oj.uz

Submission #165456

# Submission time Handle Problem Language Result Execution time Memory
165456 2019-11-27T10:33:11 Z EntityIT Plahte (COCI17_plahte) C++14
160 / 160
 674 ms 96120 KB 
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;
const int MAX = 1e9;

int n, m, Cnt;
vector<array<int, 5> > paper;
vector<array<int, 3> > p;
vector<int> comC, par, nChi, ans, cnt;
vector<bool> mark;
vector<vector<int> > col, gr;

struct Node {
    int lC, rC;
    vector<int> cover;
    Node() { lC = rC = 0; cover.clear(); }
};

struct It {
    vector<Node> node;
    It() { node.assign(1, Node() ); }

    void add(int l, int r, int val, int i = 0, int Left = 1, int Right = MAX) {
        if (r < Left || Right < l) return ;
        if (l <= Left && Right <= r) {
            node[i].cover.emplace_back(val);
            return ;
        }
        int Mid = (Left + Right) >> 1;
        if (!node[i].lC) node[i].lC = sz(node), node.emplace_back(Node() );
        if (!node[i].rC) node[i].rC = sz(node), node.emplace_back(Node() );
        add(l, r, val, node[i].lC, Left, Mid);
        add(l, r, val, node[i].rC, Mid + 1, Right);
    }

    void rem(int l, int r, int val, int i = 0, int Left = 1, int Right = MAX) {
        if (r < Left || Right < l) return ;
        if (l <= Left && Right <= r) {
            assert(node[i].cover.back() == val);
            node[i].cover.pop_back();
            return ;
        }
        int Mid = (Left + Right) >> 1;
        if (!node[i].lC) node[i].lC = sz(node), node.emplace_back(Node() );
        if (!node[i].rC) node[i].rC = sz(node), node.emplace_back(Node() );
        rem(l, r, val, node[i].lC, Left, Mid);
        rem(l, r, val, node[i].rC, Mid + 1, Right);
    }

    int get(int pos, int i = 0, int Left = 1, int Right = MAX) {
        int ret = -1;
        if (sz(node[i].cover) ) ret = node[i].cover.back();
        int Mid = (Left + Right) >> 1;
        int tmp;
        if (pos <= Mid) tmp = node[i].lC ? get(pos, node[i].lC, Left, Mid) : -1;
        else tmp = node[i].rC ? get(pos, node[i].rC, Mid + 1, Right) : -1;
        return tmp != -1 ? tmp : ret;
    }
} it;

void calNChi(int u) {
    for (int v : gr[u]) {
        calNChi(v);
        nChi[u] += nChi[v];
    }
}

void calCnt(int u, int val) {
    for (int c : col[u]) {
        cnt[c] += val;
        if (val == 1 && cnt[c] == 1) ++Cnt;
        if (val == -1 && !cnt[c]) --Cnt;
    }
    for (int v : gr[u]) if (!mark[v]) calCnt(v, val);
}

void solve(int u, bool del) {
    int bC = -1;
    for (int v : gr[u]) if (bC == -1 || nChi[bC] < nChi[v]) bC = v;

    for (int v : gr[u]) if (v != bC) solve(v, true);
    if (bC != -1) {
        solve(bC, false);
        mark[bC] = true;
    }

    calCnt(u, 1);
    ans[u] = Cnt;
    if (bC != -1) mark[bC] = false;

    if (del) calCnt(u, -1);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    freopen("PAINT.INP", "r", stdin);
//    freopen("PAINT.OUT", "w", stdout);

    cin >> n >> m;

    for (int i = 0; i < n; ++i) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        paper.emplace_back(array<int, 5>{ a, b, d, 1, i } );
        paper.emplace_back(array<int, 5>{ c + 1, b, d, -1, i } );
    }
    sort(all(paper) );

    p.assign(m, {} );
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < 3; ++j) cin >> p[i][j];
        comC.emplace_back(p[i][2]);
    }
    sort(all(p) );

    sort(all(comC) ); comC.erase(unique(all(comC) ), comC.end() );
    for (int i = 0; i < m; ++i) p[i][2] = (int)(lower_bound(all(comC), p[i][2]) - comC.begin() );

    par.assign(n, -1);
    col.assign(n, {} );
    gr.assign(n, {} );
    auto iPaper = paper.begin();
    auto iP = p.begin();
    auto doPaper = [&]() {
        if ( (*iPaper)[3] == 1) {
            par[ (*iPaper)[4] ] = it.get( (*iPaper)[1]);
            if (par[ (*iPaper)[4] ] != -1) gr[ par[ (*iPaper)[4] ] ].emplace_back( (*iPaper)[4]);
            it.add( (*iPaper)[1],  (*iPaper)[2],  (*iPaper)[4]);
        }
        else it.rem( (*iPaper)[1],  (*iPaper)[2],  (*iPaper)[4]);
        ++iPaper;
    };
    auto doP = [&]() {
        int i = it.get( (*iP)[1]);
        if (i != -1) col[i].emplace_back( (*iP)[2]);
        ++iP;
    };
    while (iPaper != paper.end() || iP != p.end() ) {
        if (iPaper == paper.end() ) doP();
        else if (iP == p.end() ) doPaper();
        else {
            if ( (*iPaper)[0] <= (*iP)[0] ) doPaper();
            else if ( (*iPaper)[0] > (*iP)[0] ) doP();
        }
    }

    nChi.assign(n, 1);
    ans.assign(n, 0);
    cnt.assign(sz(comC), 0);
    mark.assign(n, false);
    for (int i = 0; i < n; ++i) if (par[i] == -1) calNChi(i);
    for (int i = 0; i < n; ++i) if (par[i] == -1) solve(i, true);

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

    return 0;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 24016 KB Output is correct
2 Correct 174 ms 23888 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 46396 KB Output is correct
2 Correct 241 ms 45632 KB Output is correct
3 Correct 3 ms 376 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 53364 KB Output is correct
2 Correct 380 ms 51144 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 96120 KB Output is correct
2 Correct 674 ms 91608 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 652 ms 93420 KB Output is correct
2 Correct 636 ms 91996 KB Output is correct
3 Correct 3 ms 376 KB Output is correct