FOCUS - Chuyên gia ruồi

Tác giả: khuc_tuan

Ngôn ngữ: C++

#include <iostream>
#include <iomanip>
#include <fstream>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <cmath>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <functional>
#include <ctime>
#include <cstdio>
#include <cstdarg>

using namespace std;

#define Rep(i,n) for(int i=0;i<(n);++i)
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Ford(i,a,b) for(int i=(a);i>=(b);--i)
#define Fill(a,b) memset( (a), (b), sizeof(a))
#define pb push_back
#define MP make_pair
#define fi first
#define se second

typedef pair<int,int> PII;
typedef pair<PII,PII> PP;

const int MAXN = 200020;

char buf[1000];
PP command[MAXN];
int dx[MAXN], nd;
int sum[MAXN * 4];

void add(int n, int l, int r, int pos, int v) {
	sum[n] += v;
	if(l == r) return;
	int m = (l+r) / 2;
	if(pos <= m) add( 2*n, l, m, pos, v);
	else add( 2*n+1, m+1, r, pos, v);
}

void find(int n, int l, int r, int a, int b, int &k, int &pos) {
	if(k == 0) return;
	if(a <= l && r <= b) {
		if(k > sum[n]) {
			k -= sum[n];
			return;
		}
	}
	if(l == r) {
		k = 0;
		pos = l;
		return;
	}
	int m = (l+r) / 2;
	if(a <= m) find( 2*n, l, m, a, b, k, pos);
	if(m < b) find( 2*n+1, m+1, r, a, b, k, pos);
}

int main() {
	int m;
	scanf("%d", &m);
	gets(buf);
	Rep(kk,m) {
		int x, a, b;
		gets(buf);
		if(buf[0] == '+') {
			sscanf( buf + 1, "%d", &x);
			command[kk] = MP(MP(1,x),MP(0,0));
			dx[nd++] = x;
		}
		else if(buf[0] == '-') {
			sscanf( buf + 1, "%d", &x);
			command[kk] = MP(MP(2,x),MP(0,0));
			dx[nd++] = x;
		}
		else {
			sscanf( buf + 1, "%d%d%d", &x, &a, &b);
			command[kk] = MP(MP(3,x), MP(a,b));
		}
	}	
	sort( dx, dx + nd);
	nd = unique( dx, dx + nd) - dx;
	
	Rep(k,m) {
		if(command[k].fi.fi == 1) {
			int pos = lower_bound( dx, dx + nd, command[k].fi.se) - dx;
			add( 1, 0, nd - 1, pos, 1);
		}
		else if(command[k].fi.fi == 2) {
			int pos = lower_bound( dx, dx + nd, command[k].fi.se) - dx;
			add( 1, 0, nd - 1, pos, -1);
		}
		else {
			int a, b;
			int kk = command[k].fi.se;
			a = lower_bound( dx, dx + nd, command[k].se.fi) - dx;
			b = upper_bound( dx, dx + nd, command[k].se.se) - dx;
			--b;
			
			if(a <= b) {
				int pos = -1;
				find( 1, 0, nd - 1, a, b, kk, pos);
				if(pos == -1) printf("0\n");
				else printf("%d\n", dx[pos]);
			}
			else printf("0\n");
		}
	}
	return 0;
}

Download