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