Submission #768188

#TimeUsernameProblemLanguageResultExecution timeMemory
768188danikoynovPlahte (COCI17_plahte)C++14
0 / 160
2081 ms462516 KiB
/** ____ ____ ____ ____ ____ ____ ||l |||e |||i |||n |||a |||d || ||__|||__|||__|||__|||__|||__|| |/__\|/__\|/__\|/__\|/__\|/__\| **/ #include<bits/stdc++.h> #define endl '\n' using namespace std; typedef long long ll; void speed() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); } struct node { stack < pair < int, int > > st; }; const int maxn = 40100; stack < pair < int, int > > tree[8 * maxn]; void update(int root, int left, int right, int qleft, int qright, int val, int tm) { if (left > qright || right < qleft) return; if (left >= qleft && right <= qright) { if (val == -1) tree[root].pop(); else tree[root].push({tm, val}); return; } int mid = (left + right ) / 2; update(root * 2, left, mid, qleft, qright, val, tm); update(root * 2 + 1, mid + 1, right, qleft, qright, val, tm); } pair < int, int > query(int root, int left, int right, int pos) { pair < int, int > ans = {-1e9, -1}; if (!tree[root].empty()) ans = max(ans, tree[root].top()); if (left == right) return ans; int mid = (left + right) / 2; if (pos <= mid) ans = max(ans, query(root * 2, left, mid, pos)); else ans = max(ans, query(root * 2 + 1, mid + 1, right, pos)); return ans; } struct point { int x, y; void input() { cin >> x >> y; } }; struct rectangle { point A, B; void input() { A.input(); B.input(); } }; struct line { point cor; int len, type, idx; }; int n, m, col[maxn]; rectangle r[maxn]; point s[maxn]; void read_data() { cin >> n >> m; for (int i = 1; i <= n; i ++) r[i].input(); for (int i = 1; i <= m; i ++) s[i].input(), cin >> col[i]; } int xcor, ycor; void compress_data() { vector < int > dx, dy, dc; for (int i = 1; i <= n; i ++) { dx.push_back(r[i].A.x); dx.push_back(r[i].B.x); dy.push_back(r[i].A.y); dy.push_back(r[i].B.y); } for (int i = 1; i <= m; i ++) { dx.push_back(s[i].x); dy.push_back(s[i].y); dc.push_back(col[i]); } sort(dx.begin(), dx.end()); sort(dy.begin(), dy.end()); sort(dc.begin(), dc.end()); dx.erase(unique(dx.begin(), dx.end()), dx.end()); dy.erase(unique(dy.begin(), dy.end()), dy.end()); dc.erase(unique(dc.begin(), dc.end()), dc.end()); xcor = dx.size(); ycor = dy.size(); unordered_map < int, int > mx, my, mc; for (int i = 0; i < dx.size(); i ++) mx[dx[i]] = i + 1; for (int i = 0; i < dy.size(); i ++) my[dy[i]] = i + 1; for (int i = 0; i < dc.size(); i ++) mc[dc[i]] = i + 1; for (int i = 1; i <= n; i ++) { r[i].A.x = mx[r[i].A.x]; r[i].A.y = my[r[i].A.y]; r[i].B.x = mx[r[i].B.x]; r[i].B.y = my[r[i].B.y]; } for (int i = 1; i <= m; i ++) { s[i].x = mx[s[i].x]; s[i].y = my[s[i].y]; col[i] = mc[col[i]]; } } bool cmp(const line &l1, const line &l2) { if (l1.cor.x != l2.cor.x) return l1.cor.x < l2.cor.x; return l1.type > l2.type; } void creat_events(vector < line > &events) { for (int i = 1; i <= n; i ++) { line l; l.cor.x = r[i].A.x; l.cor.y = r[i].A.y; l.idx = i; l.len = r[i].B.y - r[i].A.y; l.type = 1; events.push_back(l); l.cor.x = r[i].B.x; l.type = -1; events.push_back(l); } for (int i = 1; i <= m; i ++) { line l; l.cor = s[i]; l.len = 0; l.type = 0; l.idx = i; events.push_back(l); } sort(events.begin(), events.end(), cmp); } vector < int > adj[maxn]; int sub[maxn]; bitset < maxn > bt[maxn]; void sweep_line() { vector < line > events; creat_events(events); for (int i = 0; i < events.size(); i ++) { line cur = events[i]; ///cout << "event " << i << " " << cur.type << " " << cur.cor.x << " " << cur.cor.y << " " << cur.cor.y + cur.len << endl; if (cur.type == 1) { int par = query(1, 1, ycor, cur.cor.y).second; if (par != -1) adj[par].push_back(cur.idx); update(1, 1, ycor, cur.cor.y, cur.cor.y + cur.len, cur.idx, i); } else if (cur.type == -1) { update(1, 1, ycor, cur.cor.y, cur.cor.y + cur.len, -1, -1); } else { int par = query(1, 1, ycor, cur.cor.y).second; if (par != -1) bt[par][col[cur.idx]] = 1; ///cout << "here " << par << endl; } } } int used[maxn]; void dfs(int v) { used[v] = 1; for (int u : adj[v]) { if (used[u]) continue; dfs(u); bt[v] |= bt[u]; } } void traverse_graph() { for (int i = 1; i <= n; i ++) if (!used[i]) dfs(i); for (int i = 1; i <= n; i ++) cout << bt[i].count() << endl; } void solve() { read_data(); compress_data(); sweep_line(); traverse_graph(); } int main() { solve(); return 0; }

Compilation message (stderr)

plahte.cpp: In function 'void compress_data()':
plahte.cpp:136:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for (int i = 0; i < dx.size(); i ++)
      |                     ~~^~~~~~~~~~~
plahte.cpp:138:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |     for (int i = 0; i < dy.size(); i ++)
      |                     ~~^~~~~~~~~~~
plahte.cpp:140:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |     for (int i = 0; i < dc.size(); i ++)
      |                     ~~^~~~~~~~~~~
plahte.cpp: In function 'void sweep_line()':
plahte.cpp:204:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |     for (int i = 0; i < events.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~
#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...