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); }