/* -*- coding: utf-8 -*- * * 678.cc: No.678 2Dシューティングゲームの必殺ビーム - yukicoder */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; /* constant */ const int MAX_N = 188; const int W = 1280; const int MAX_E2 = 1 << 12; // 4096 const int INF = 1 << 30; /* typedef */ template struct SegTreeBool { int n, e2; bool nodes[MAX_E2]; SegTreeBool() {} void init(int _n) { n = _n; for (e2 = 1; e2 < n; e2 <<= 1); fill(nodes, nodes + MAX_E2, false); } void set_range(int r0, int r1, int k, int i0, int i1) { if (r1 <= i0 || i1 <= r0) return; if (r0 <= i0 && i1 <= r1) { nodes[k] = true; return; } int im = (i0 + i1) / 2, k0 = k * 2 + 1, k1 = k0 + 1; set_range(r0, r1, k0, i0, im); set_range(r0, r1, k1, im, i1); nodes[k] = (nodes[k0] & nodes[k1]); } void set_range(int r0, int r1) { set_range(r0, r1, 0, 0, e2); } bool min_range(int r0, int r1, int k, int i0, int i1) { if (r1 <= i0 || i1 <= r0) return true; if (r0 <= i0 && i1 <= r1) return nodes[k]; int im = (i0 + i1) / 2, k0 = k * 2 + 1, k1 = k0 + 1; nodes[k0] |= nodes[k], nodes[k1] |= nodes[k]; bool v0 = min_range(r0, r1, k0, i0, im); bool v1 = min_range(r0, r1, k1, im, i1); return (v0 & v1); } bool min_range(int r0, int r1) { return min_range(r0, r1, 0, 0, e2); } }; struct Enemy { int xl, xr, y, i; Enemy() {} Enemy(int _xl, int _xr, int _y, int _i): xl(_xl), xr(_xr), y(_y), i(_i) {} bool operator<(const Enemy &e) const { return y < e.y || (y == e.y && xl < e.xl); } }; /* global variables */ SegTreeBool st; Enemy es[MAX_N]; int hs[MAX_N]; /* subroutines */ /* main */ int main() { int n, xlb, xrb; scanf("%d%d%d", &n, &xlb, &xrb); st.init(W); st.set_range(0, xlb - 1); st.set_range(xrb, W); for (int i = 0; i < n; i++) { int xl, yu, xr, yd; scanf("%d%d%d%d", &xl, &yu, &xr, &yd); xl = max(xl - 1, 0); xr = min(xr, W); es[i] = Enemy(xl, xr, yd, i); } sort(es, es + n); for (int i = n - 1; i >= 0; i--) { Enemy &ei = es[i]; bool mv = st.min_range(ei.xl, ei.xr); //printf("%d: %d-%d,%d %d\n", ei.i, ei.xl, ei.xr, ei.y, mv); if (! mv) { hs[ei.i] = 1; st.set_range(ei.xl, ei.xr); //printf("%d\n", st.min_range(ei.xl, ei.xr)); } } for (int i = 0; i < n; i++) printf("%d\n", hs[i]); return 0; }