JOI春合宿 2010-day3 Hide-and-seek

問題文 : かくれんぼ

解法 :
障害物の左上の座標についてそれらを昇順ソートし, 各x座標について障害物の重なりの大きさを持つ.
そして、実際に障害物をフィールドに挿入していく.
その過程で武器を防げるだけの大きさになれば、その座標を出力する.

ここで、障害物の挿入・最大値の取得はStarry Sky木を用いて行った.

コード :

#include <cstdio>
#include <vector>
using namespace std;

typedef struct {
	int x, x2;
	int y;
	int val;
} Point;

int pSeg[1 << 19];
Point mSeg[1 << 19];

bool operator < (const Point &a, const Point &b)
{
	if (a.y - b.y){
		return (a.y < b.y);
	}
	return (a.x < b.x);
}

void add(int a, int b, int k, int l, int r)
{
	if (b <= l || r <= a){
		return;
	}
	
	if (a <= l && r <= b){
		pSeg[k] += 1;
		if (!mSeg[k].x) mSeg[k].x = l;
		while (k){
			k = (k - 1) / 2;
			if (mSeg[k * 2 + 1].val + pSeg[k * 2 + 1] >= mSeg[k * 2 + 2].val + pSeg[k * 2 + 2]){
				mSeg[k] = mSeg[k * 2 + 1];
				mSeg[k].val += pSeg[k * 2 + 1];
			}
			else {
				mSeg[k] = mSeg[k * 2 + 2];
				mSeg[k].val += pSeg[k * 2 + 2];
			}
		}
	}
	else {
		add(a, b, k * 2 + 1, l, (l + r) / 2);
		add(a, b, k * 2 + 2, (l + r) / 2, r);
	}
}

Point null;

Point getMax(int a, int b, int k, int l, int r)
{
	if (b <= l || r <= a){
		return (null);
	}
	
	Point ret;
	if (a <= l && r <= b){
		ret = mSeg[k];
		ret.val += pSeg[k];
		return (ret);
	}
	Point lch = getMax(a, b, k * 2 + 1, l, (l + r) / 2);
	Point rch = getMax(a, b, k * 2 + 2, (l + r) / 2, r);
	if (lch.val >= rch.val){
		ret = lch;
	}
	else {
		ret = rch;
	}
	ret.val += pSeg[k];
	
	return (ret);
}

int main()
{
	int N, M;
	static Point dat[50000], ans[50000];
	static pair<int, int> dmg[50000];
	
	scanf("%d %d", &N, &M);
	
	for (int i = 0; i < N; i++){
		scanf("%d %d %d", &dat[i].x, &dat[i].y, &dat[i].x2);
		dat[i].x2 += dat[i].x - 1;
	}
	
	sort(dat, dat + N);
	
	for (int i = 1 << 18; i < 1 << 19; i++){
		mSeg[i].x = i - (1 << 18) + 1;
	}
	
	for (int i = 0; i < M; i++){
		scanf("%d", &dmg[i].first);
		dmg[i].second = i;
	}
	
	sort(dmg, dmg + M);
	Point m = null;
	int idx = 0;
	for (int i = 0; i < M; i++){
		while (idx != N && m.val <= dmg[i].first){
			add(dat[idx].x, dat[idx].x2 + 1, 0, 0, 1 << 18);
			m = getMax(dat[idx].x, dat[idx].x2 + 1, 0, 0, 1 << 18);
			m.y = dat[idx++].y;
		}
		if (m.val > dmg[i].first){
			ans[dmg[i].second] = m;
		}
		else {
			ans[dmg[i].second].x = ans[dmg[i].second].y = -1;
		}
	}
	
	for (int i = 0; i < M; i++){
		printf("%d %d\n", ans[i].x, ans[i].y);
	}
	
	return (0);
}