View Code of Problem 1093

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 1000000
using namespace std;

struct Complex{
	int x,y;
	bool operator <(const Complex &a)const {
		return x < a.x;
	}
}cow[MAX];
struct BigHeap{
	int num[MAX],last;
	int Top() {
		return num[1];
	}
	void Insert(int x) {
		num[++last] = x;
		int now = last;
		while(num[now] > num[now >> 1] && now > 1)
			swap(num[now],num[now >> 1]),now >>= 1;
	}
	void Pop() {
		num[1] = num[last--];
		int now = 2;
		while(now <= last) {
			if(num[now] < num[now + 1])	now++;
			if(num[now] > num[now >> 1])	swap(num[now],num[now >> 1]),now <<= 1;
			else	break;
		}
	}
	void Clear() {
		last = 0;
	}
}heap;

int points,select,limit;
int sum[MAX];

int main()
{
	cin >> select >> points >> limit;
	for(int i = 1;i <= points; ++i)
		scanf("%d%d",&cow[i].x,&cow[i].y);
	sort(cow + 1,cow + points + 1);
	select >>= 1;
	int temp = 0;
	for(int i = 1;i <= select; ++i) {
		temp += cow[i].y;
		heap.Insert(cow[i].y);
	}
	sum[select + 1] = temp;
	for(int i = select + 1;i < points; ++i) {
		heap.Insert(cow[i].y);
		temp += cow[i].y;
		temp -= heap.Top();
		heap.Pop();
		sum[i + 1] = temp;
	}
	temp = 0,heap.Clear();
	for(int i = points;i > points - select; --i) {
		temp += cow[i].y;
		heap.Insert(cow[i].y);
	}
	sum[points - select] += temp;
	for(int i = points - select;i >= select; --i) {
		heap.Insert(cow[i].y);
		temp += cow[i].y;
		temp -= heap.Top();
		heap.Pop();	
		sum[i - 1] += temp;	
	}
	int ans = -1;
	for(int i = points - select;i >= select + 1; --i)
		if(sum[i] + cow[i].y <= limit) {
			ans = cow[i].x;
			break;
		}
	cout << ans << endl;
	return 0;
}