Submission #165456

#TimeUsernameProblemLanguageResultExecution timeMemory
165456EntityITPlahte (COCI17_plahte)C++14
160 / 160
674 ms96120 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...