Coders

#include <iostream>
#include <set>
#include <algorithm>

#define ll long long
#define F first
#define S second

using namespace std;

int n,m;
ll c;
pair<int, ll> a[101010];
set<pair<ll, int>> sbeg, slef,srig;

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n >> m >> c;
	for (int i=0;i<n;i++) {
		int q;
		ll s;
		cin >> q >> s;
		a[i] = make_pair(q,s);
	}
	sort(a,a+n);
	ll sum=0;
	for (int i=0;i<(m-1)/2;i++) {
		srig.insert(make_pair(a[n-i-1].S,a[n-i-1].F));
		sum += a[n-i-1].S;
	}
	pair<ll, int> mid = make_pair(a[n-(m+1)/2].S,a[n-(m+1)/2].F);
	sum += a[n-(m+1)/2].S;
	for (int i=0;i<n-(m+1)/2;i++)
		sbeg.insert(make_pair(a[i].S,a[i].F));
	for (int i=0;i<(m-1)/2;i++) {
		pair<ll, int> p = *sbeg.begin();
		sbeg.erase(p);
		slef.insert(p);
		sum += p.F;
	}
	int ind = n-(m+1)/2-1;
	while (sum>c && ind >= 0) {
		auto it = srig.end();
		it--;
		if (mid.F < (*it).F) {
			pair<ll, int> p1 = *it;
			srig.erase(p1);
			sum -= p1.F;
			srig.insert(mid);
		}
		else {
			sum-= mid.F;
		}
		mid = make_pair(a[ind].S,a[ind].F);
		ind--;
		if (sbeg.count(mid)) {
			sbeg.erase(mid);
			sum+=mid.F;
		} else {
			slef.erase(mid);
			if (sbeg.empty()) break;
			pair<ll, int> p2 =  *sbeg.begin();
			sbeg.erase(p2);
			slef.insert(p2);
			sum+=p2.F;
		}
	}
	if (sum <= c) cout << mid.S << "\n";
	else cout << "QAQ\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED