JOI 春合宿 2010 Day 3 Hide-and-seek(かくれんぼ)

Starry Sky Treeで最大値のindexがわからない〜って言ってて、英語の授業中に根からたどればいいだけという事に気付いた時に本当に自分には頭がないのだなぁと思った

— 894 (@okuraofvegetabl) 2014, 5月 29

obstacleたちをソートして、順番に処理していく。
足す作業はStarry Sky Treeでやる。後から思ったけど、別に遅延評価する必要ない。(2つの配列に分けてもできる、詳しくは蟻本参照)
最大値のindexの求め方がわかってからはやるだけだった…(つらい)

const int SIZE=1<<18;
struct segtree
{
	int seg[SIZE*2],lazy[SIZE*2];
	void lazy_evaluate(int k)
	{
		seg[k]+=lazy[k];
		if(k<SIZE-1)
		{
			lazy[k*2+1]+=lazy[k];
			lazy[k*2+2]+=lazy[k];
		}
		lazy[k]=0;
		return;
	}
	void update(int a,int b,int k,int l,int r,int x)
	{
		lazy_evaluate(k);
		if(r<=a||b<=l)return;
		else if(a<=l&&r<=b)
		{
			lazy[k]+=x;
			lazy_evaluate(k);
			return ;
		}
		else
		{
			update(a,b,k*2+1,l,(l+r)/2,x);
			update(a,b,k*2+2,(l+r)/2,r,x);
			seg[k]=max(seg[k*2+1],seg[k*2+2]);
			return;
		}
	}
	int get_max(){return seg[0]+lazy[0];}
	int find(int x)
	{
		if(x>get_max())return -1;
		int now=0;
		while(1)
		{
			lazy_evaluate(now);
			if(now>=SIZE-1)return now-(SIZE-1);
			int lch=now*2+1,rch=now*2+2;
			if(seg[lch]+lazy[lch]>=x)now=lch;
			else now=rch;
		}
	}
}sst;
struct obst
{
	int x,y,len;
};
bool comp(obst a,obst b)
{
	if(a.y!=b.y)return a.y < b.y;
	else return a.x < b.x;
}
int n,q;
int main()
{
	scanf("%d %d",&n,&q);
	vector<obst> vec(n);
	vector<P> query(q);
	vector<P> ans(q);
	for(int i=0;i<n;i++)cin >> vec[i].x >> vec[i].y >> vec[i].len;
	for(int i=0;i<q;i++)
	{
		cin >> query[i].fi;
		query[i].sec=i;
	}
	sort(vec.begin(),vec.end(),comp);
	sort(query.begin(),query.end());
	int pos=0;
	for(int i=0;i<vec.size();i++)
	{
		sst.update(vec[i].x,vec[i].x+vec[i].len,0,0,SIZE,1);
		//cout << i << ' ' << sst.get_max() << endl;
		while(pos<query.size()&&query[pos].fi<sst.get_max())
		{
			ans[query[pos].sec].sec=vec[i].y;
			ans[query[pos].sec].fi=sst.find(query[pos].fi+1);
			pos++;
		}
	}
	P na=P(0,0);
	for(int i=0;i<ans.size();i++)
	{
		if(ans[i]==na)cout << "-1 -1" << endl;
		else cout << ans[i].fi << ' ' << ans[i].sec << endl;
	}
	return 0;
}