Submission #138875

#TimeUsernameProblemLanguageResultExecution timeMemory
138875KCSCPlahte (COCI17_plahte)C++14
160 / 160
864 ms73408 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = (a); i < int(b); ++i) #define REP(i, n) for (int i = 0; i < int(n); ++i) #define ALL(x) (x).begin(), (x).end() const int DIM = 250005; struct Event { int a, b, c, d; }; vector<Event> events; vector<pair<int, int>> segTree[DIM * 4]; set<int> colorSet[DIM]; vector<int> posList, graph[DIM]; int answer[DIM], whatSet[DIM]; inline bool cmp(Event &e1, Event &e2) { if (e1.b != e2.b) return e1.b < e2.b; return e1.a < e2.a; } void update(int nd, int le, int ri, int st, int en, pair<int, int> vl) { if (st <= le and ri <= en) { if (vl.first == -2) segTree[nd].pop_back(); else segTree[nd].push_back(vl); } else { int md = (le + ri) / 2; if (st <= md) update(nd * 2, le, md, st, en, vl); if (md < en) update(nd * 2 + 1, md + 1, ri, st, en, vl); } } pair<int, int> query(int nd, int le, int ri, int ps) { if (le == ri) { if (segTree[nd].empty()) return make_pair(-2, -2); else return segTree[nd].back(); } else { pair<int, int> aux; int md = (le + ri) / 2; if (ps <= md) aux = query(nd * 2, le, md, ps); else aux = query(nd * 2 + 1, md + 1, ri, ps); if (segTree[nd].empty()) return aux; else if (aux.first < segTree[nd].back().first) return segTree[nd].back(); else return aux; } } void merge(int a, int b) { if (colorSet[whatSet[a]].size() > colorSet[whatSet[b]].size()) swap(a, b); for (int x : colorSet[whatSet[a]]) colorSet[whatSet[b]].insert(x); whatSet[a] = whatSet[b]; } void dfs(int x) { int sz = -1, ps = -1; for (int y : graph[x]) { dfs(y); merge(x, y); } answer[x] = colorSet[whatSet[x]].size(); } int main(void) { #ifdef HOME freopen("plahte.in", "r", stdin); freopen("plahte.out", "w", stdout); #endif int n, m; cin >> n >> m; static int LIM = 2 * n + m; REP(i, n) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; events.push_back({i, x1, y1, y2}); events.push_back({-1, x2 + 1, y1, y2}); posList.push_back(y1); posList.push_back(y2); } REP(i, m) { int x, y, c; cin >> x >> y >> c; events.push_back({LIM, x, y, c}); posList.push_back(y); } events.push_back({n, -1, 0, LIM}); sort(posList.begin(), posList.end()); sort(events.begin(), events.end(), cmp); posList.erase(unique(ALL(posList)), posList.end()); for (Event &e : events) { if (e.a != n) { e.c = lower_bound(ALL(posList), e.c) - posList.begin(); if (e.a != LIM) e.d = lower_bound(ALL(posList), e.d) - posList.begin(); } if (e.a == -1) update(1, 0, LIM, e.c, e.d, make_pair(-2, -2)); else if (e.a < LIM) { graph[query(1, 0, LIM, e.c).second].push_back(e.a); update(1, 0, LIM, e.c, e.d, make_pair(e.b, e.a)); } else colorSet[query(1, 0, LIM, e.c).second].insert(e.d); } REP(i, n + 1) whatSet[i] = i; dfs(n); REP(i, n) cout << answer[i] << "\n"; return 0; }

Compilation message (stderr)

plahte.cpp: In function 'void dfs(int)':
plahte.cpp:72:6: warning: unused variable 'sz' [-Wunused-variable]
  int sz = -1, ps = -1;
      ^~
plahte.cpp:72:15: warning: unused variable 'ps' [-Wunused-variable]
  int sz = -1, ps = -1;
               ^~
#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...