4bitにっき

ぽよ

JOI2010春合宿Day3 かくれんぼ (Hide-and-seek)

眠いです。

解法

最もy座標が小さくその中でx座標が小さいものを求めろと言われているので、とりあえず障害物をそのような順でソートします。
そうすると、ソートした順で障害物を追加していって各攻撃力に耐えられるx座標を見つけた時が答えになります。

今最大の攻撃力に耐えられるx座標がどこかを管理しなければいけませんが、これはとてもStarry Sky Tree(区間に対して一様な加減算などができるセグ木)を使いたいですね。
x座標の制約は小さいので座圧などもいらずそのまま配列で持つことができます。

実装

mapを使っていたがために同じ入力が来るとバグってしまっていたのですが、全ケースWAしていたのでもっとやばいミスだろうと探していました。
ところがそれを直すだけで全ケースACに変わったのでたまげました。


map使ってるのは実装を考えるのをサボりたかったというだけなので、クエリをソートしてほげするべきだと思います。


Starry Sky Treeはせっかくなので遅延セグ木で書きました。
前記事に書いた遅延セグ木の書き方が気に入ってます。

using namespace std;

#define int long long

const int MAX_N = 5*1e5, MAX_M = 5*1e5, MAX_X = 1 << 18;

struct Node
{
	pair<int, int> v;
	int laziness;
};

struct Wall
{
	int x, y, w;
	bool operator < (const Wall &a) const
	{
		return (y == a.y) ? x < a.x : y < a.y;
	}
};

int N, M, a[MAX_M];
int ansX[MAX_M], ansY[MAX_M];
Wall wall[MAX_N];
Node seg[MAX_X*2 - 1];
int segSize;

void InitNode(int l, int r, int k)
{
	seg[k].v.second = -l;
	if (k >= segSize - 1) return;
	InitNode(l, (l + r)/2, k*2 + 1);
	InitNode((l + r)/2, r, k*2 + 2);
}

void Init()
{
	segSize = MAX_X;
	InitNode(0, segSize, 0);
}

inline void UpdateLaziness(int k)
{
	seg[k*2 + 1].laziness += seg[k].laziness;
	seg[k*2 + 2].laziness += seg[k].laziness;
	seg[k].v.first += seg[k].laziness;
	seg[k].laziness = 0;
}

pair<int, int> Add(int l, int r, int k, int a, int b, int v)
{
	if (r <= a || b <= l) return make_pair(seg[k].v.first + seg[k].laziness, seg[k].v.second);
	if (a <= l && r <= b) return make_pair(seg[k].v.first + (seg[k].laziness += v), seg[k].v.second);
	UpdateLaziness(k);
	return seg[k].v = max(Add(l, (l + r)/2, k*2 + 1, a, b, v), Add((l + r)/2, r, k*2 + 2, a, b, v));
}

pair<int, int> GetMax()
{
	return seg[0].v;
}

signed main()
{
	map<int, vector<int> > query;
	cin >> N >> M;
	Init();
	fill(ansX, ansX + M, -1ll);
	fill(ansY, ansY + M, -1ll);
	for (int i = 0; i < N; i++)
	{
		cin >> wall[i].x >> wall[i].y >> wall[i].w;
	}
	for (int i = 0; i < M; i++)
	{
		cin >> a[i];
		query[a[i]].push_back(i);
	}

	sort(wall, wall + N);

	for (int i = 0; i < N; i++)
	{
		Add(0, segSize, 0, wall[i].x, wall[i].x + wall[i].w, 1);
		pair<int, int> ret = GetMax();
		map<int, vector<int> >::iterator itr = query.find(ret.first - 1);
		if (itr == query.end()) continue;
		for (int j = 0; j < itr->second.size(); j++)
		{
			ansX[itr->second[j]] = -ret.second;
			ansY[itr->second[j]] = wall[i].y;
		}
		query.erase(itr);
	}
	for (int i = 0; i < M; i++)
	{
		printf("%lld %lld\n", ansX[i], ansY[i]);
	}
	return 0;
}