oj.uz

Submission #234610

# Submission time Handle Problem Language Result Execution time Memory
234610 2020-05-24T19:15:55 Z ne4eHbKa Plahte (COCI17_plahte) C++17
96 / 160
 2000 ms 230148 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

#define re return
#define ft first
#define sd second

#pragma GCC optimize("O3")

mt19937 rnd(chrono::system_clock().now().time_since_epoch().count());

int rint(int v) {re rnd() % v;}

const int N = 8e4 + 5;

int n, m, mxx, mxy, mxc;
vector<int> p;
vector<ll> area;

map<int, int> shrink_x, shrink_y, shrink_c;

struct rect {
    int x, y, X, Y;
    rect() {
        cin >> x >> y >> X >> Y;
        shrink_x[x], shrink_x[X];
        shrink_y[y], shrink_y[Y];
    }
    void init(ll *a) {
        x = shrink_x[x];
        X = shrink_x[X];
        y = shrink_y[y];
        Y = shrink_y[Y];
        (*a = X - x) *= (ll)Y - y;
    }
};

vector<rect> rects;

struct ball {
    int x, y, c;
    ball() {
        cin >> x >> y >> c;
        shrink_x[x];
        shrink_y[y];
        shrink_c[c];
    }
    void init() {
        x = shrink_x[x];
        y = shrink_y[y];
        c = shrink_c[c];
    }
};

vector<ball> balls;

struct cmp {
    bool operator() (const int &a, const int &b) const {
        return area[a] == area[b]
            ? a < b
            : area[a] < area[b];
    }
};

int cur, upper_rect;

struct tree {
    tree *l, *r;
    set<int, cmp> v {}, f {};
    tree(int tl = 0, int tr = mxy - 1): l(r = 0) {
        if(tl < tr) {
            int tm = (tl + tr) >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
        }
    }
    void add(int ql, int qr, int tl = 0, int tr = mxy - 1) {
        if(ql > qr) re;
        if(!f.empty()) {
            int u = *f.begin();
            if(upper_rect < 0 || area[upper_rect] > area[u])
                upper_rect = u;
        }
        if(ql == tl && qr == tr) {
            f.insert(cur);
            if(!v.empty()) {
                int u = *v.begin();
                if(upper_rect < 0 || area[upper_rect] > area[u])
                    upper_rect = u;
            }
        } else {
            v.insert(cur);
            int tm = (tl + tr) >> 1;
            l->add(ql, min(qr, tm), tl, tm);
            r->add(max(tm + 1, ql), qr, tm + 1, tr);
        }
    }
    void del(int ql, int qr, int tl = 0, int tr = mxy - 1) {
        if(ql > qr) re;
        if(ql == tl && qr == tr) re void(f.erase(cur));
        v.erase(cur);
        if(tl < tr) {
            int tm = (tl + tr) >> 1;
            l->del(ql, min(qr, tm), tl, tm);
            r->del(max(tm + 1, ql), qr, tm + 1, tr);
        }
    }
    void shoot(int p, int tl = 0, int tr = mxy - 1) {
        if(!f.empty()) {
            int u = *f.begin();
            if(cur < 0 || area[cur] > area[u])
                cur = u;
        }
        if(tl == tr) re;
        int tm = (tl + tr) >> 1;
        p <= tm
            ? l->shoot(p, tl, tm)
            : r->shoot(p, tm + 1, tr);
    }
};

vector<int> g[N];
vector<int> nodes[N];

int l[N + N], r[N + N], timer, st[18][N + N], h[N], lg[N + N], rt[N], root;

void rec(int v, int he = 0) {
    rt[v] = root, h[v] = he;
    st[0][l[v] = r[v] = timer++] = v;
    for(const int &u : g[v]) {
        rec(u, he + 1);
        st[0][r[v] = timer++] = v;
    }
}

int mn(int a, int b) {re h[a] < h[b] ? a : b;}

void build_sparse() {
    for(int i = 0; i < N + N; ++i) lg[i] = !i ? 0 : lg[i - 1] + (1 << lg[i - 1] + 1 <= i);
    for(int j = 1; j < 18; ++j) for(int i = 0; i + (1 << j) - 1 < N + N; ++i)
        st[j][i] = mn(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
}

int lca(int a, int b) {
    if(l[a] > l[b]) swap(a, b);
    if(r[a] >= r[b]) re a;
    int f = lg[r[b] - l[a] + 1];
    re mn(st[f][l[a]], st[f][r[b] - (1 << f) + 1]);
}

int z[N];
int count(int v) { for(int u : g[v]) z[v] += count(u); re z[v]; }

int main() {
#ifdef _LOCAL
    freopen("10.in", "r", stdin);
    freopen("10.out", "w", stdout);
#endif // _LOCAL

    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; ++i) rects.emplace_back();
    for(int i = 0; i < m; ++i) balls.emplace_back();

    for(auto t : shrink_x) shrink_x[t.ft] = mxx++;
    for(auto t : shrink_y) shrink_y[t.ft] = mxy++;
    for(auto t : shrink_c) shrink_c[t.ft] = mxc++;

    area.resize(n);
    ll *pt_a = &area[0];
    for(auto &t : rects) t.init(pt_a++);
    for(auto &t : balls) t.init();

    tree t {};

    vector<int> rect_add(n);
    for(int i = 0; i < n; ++i) rect_add[i] = i;
    sort(rect_add.begin(), rect_add.end(),
        [&] (const int &a, const int &b) {return rects[a].x != rects[b].x
            ? rects[a].x < rects[b].x
            : area[a] > area[b];});

    vector<int> rect_del = rect_add;
    sort(rect_del.begin(), rect_del.end(),
        [&] (const int &a, const int &b) {return rects[a].X < rects[b].X;});

    vector<int> shot(m);
    for(int i = 0; i < m; ++i) shot[i] = i;
    sort(shot.begin(), shot.end(),
        [&] (const int &a, const int &b) {return balls[a].x < balls[b].x;});

    p.assign(n, -1);

    int ai = 0, di = 0, si = 0;
    for(int x = 0; x < mxx; ++x) {
        for(; ai < n && rects[rect_add[ai]].x == x; ++ai) {
            cur = rect_add[ai];
            upper_rect = -1;
            t.add(rects[cur].y, rects[cur].Y);
            p[cur] = upper_rect;
//            cerr << "add " << rects[cur].y << ' ' << rects[cur].Y << endl;
        }
        for(; si < m && balls[shot[si]].x == x; ++si) {
            cur = -1;
            t.shoot(balls[shot[si]].y);
            if(~cur) nodes[balls[shot[si]].c].push_back(cur);
//            cerr << "shoot " << balls[shot[si]].c << ' ' << balls[shot[si]].y << endl;
        }
        for(; di < n && rects[rect_del[di]].X == x; ++di) {
            cur = rect_del[di];
            t.del(rects[cur].y, rects[cur].Y);
//            cerr << "del " << rects[cur].y << ' ' << rects[cur].Y << endl;
        }
    }

    for(int i = 0; i < n; ++i) if(~p[i]) g[p[i]].push_back(i);

    for(int i = 0; i < n; ++i) if(p[i] < 0) root = i, rec(i);

    build_sparse();

    for(int c = 0; c < mxc; c++) {
        vector<int> &ns = nodes[c];
        sort(ns.begin(), ns.end(), [&] (const int &a, const int &b) {return l[a] < l[b];});
        int v = -1;
        for(int i : ns) v < 0 || rt[v] != rt[i]
                            ? z[v = i]++
                            : (z[i]++, z[lca(i, v)]--, v = i);
    }

    for(int i = 0; i < n; ++i) if(p[i] < 0) count(i);

    for(int i = 0; i < n; ++i) cout << z[i] << '\n';
}

Compilation message

plahte.cpp: In function 'void build_sparse()':
plahte.cpp:145:81: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
     for(int i = 0; i < N + N; ++i) lg[i] = !i ? 0 : lg[i - 1] + (1 << lg[i - 1] + 1 <= i);
                                                                       ~~~~~~~~~~^~~
plahte.cpp:147:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
         st[j][i] = mn(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
                                                         ~~^~~

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 49620 KB Output is correct
2 Correct 359 ms 42220 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 84020 KB Output is correct
2 Correct 570 ms 63540 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1220 ms 147172 KB Output is correct
2 Correct 973 ms 82008 KB Output is correct
3 Correct 15 ms 14464 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2092 ms 230148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 205296 KB Time limit exceeded
2 Halted 0 ms 0 KB -