読者です 読者をやめる 読者になる 読者になる

JOI 2010 春合宿 day3-2 「Hide-and-Seek」

デバッグに時間がかかりまくった。
セグメント木の応用かな。

#include<cstdio>
#include<vector>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
#define pb push_back
using namespace std;

struct wall{int y, a, b;};
struct seg{int k, a, b;};
struct rem{int x, y, k;};

bool comp_y(const wall& a, const wall& b){return a.y < b.y;}

seg st[1<<17];
vector<wall> wa;
vector<rem> mem;
int n2, ne, ca, cb;

void init(){
	int nn2 = n2;
	rep(i,ne+1){
		int n3 = 1 << i;
		rep(j,n3){
			st[n3+j].a = j * nn2 + 1;
			st[n3+j].b = (j+1) * nn2;
		}
		nn2 >>= 1;
	}
	return;
}


bool check(int i){
	if(st[i].a > cb || st[i].b < ca) return false;
	if (st[i].k) return false;
	if(st[i].a >= ca && st[i].b <= cb) return true;
	return check(i<<1) | check((i<<1)+1);
}


void add(bool bl, int i){
	if(st[i].a > cb || st[i].b < ca){
		if(!bl) st[i].k ++;
		return;
	}
	
	if(bl && st[i].k){st[i].k--; bl = false;}
	if(st[i].a >= ca && st[i].b <= cb) return;
	
	int l = i<<1, r = l + 1;
	add(bl, l); add(bl, r);
	if(st[l].k && st[r].k){st[l].k --; st[r].k --; st[i].k ++;}
	
	return;
}


int max_pos(){
	int i = 1, l, r;
	rep(j,ne){
		l = i << 1; r = l + 1;
		if(!st[l].k) i = l; else i = r;
	}
	
	return i - n2 + 1;
}



int main(){
	int n, m, x, y, w, a, l, r, c;
	bool bl;
	
	scanf("%d%d",&n,&m);
	
	rep(i,n){
		scanf("%d%d%d",&x,&y,&w);
		wa.pb((wall){y,x,x+w-1});
	}
	sort(wa.begin(), wa.end(), comp_y);
	
	n2 = 1<<16; ne = 16;
	init();
	
	mem.pb((rem){0,0,0});
	
	rep(i,wa.size()){
		ca = wa[i].a; cb = wa[i].b;
		bl = check(1);
		if (bl) st[0].k ++;
		add(!bl, 1);
		
		if(wa[i].y == mem[mem.size()-1].y) {
			mem[mem.size()-1] = (rem){max_pos(), wa[i].y, st[0].k};
		} else {
			mem.pb((rem){max_pos(), wa[i].y, st[0].k});
		}
	}
	
	mem.pb((rem){-1,-1,100000});
	
	rep(i,m){
		scanf("%d",&a);
		l = 0; r = mem.size()-1;
		while(l < r){
			c = (l+r)/2;
			if (a < mem[c].k) r = c; else l = c+1;
		}
		printf("%d %d\n",mem[l].x, mem[l].y);
	}
	
	return 0;
}