| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 613736 |
2022-07-30T09:59:22 Z |
Vanilla |
Plahte (COCI17_plahte) |
C++17 |
|
632 ms |
204036 KB |
#include <bits/stdc++.h>
using namespace std;typedef long long int64;const int maxn = 8e4 + 2;vector <int> ad [maxn]; int dad [2 * maxn];set <int> stl [maxn * 2];int rs [maxn];struct node {int l, r, v;int lazy = -1;node* left = NULL;node* right = NULL;node(int _l, int _r, int _v): l(_l), r(_r), v(_v) {};inline void propagate () {if (left == NULL) {int mid = (l + r) / 2;left = new node (l, mid, 0);right = new node (mid + 1, r, 0);}if (lazy != -1){left->v = left->lazy = right->v = right->lazy = lazy;lazy = -1;}}inline void update (int il, int ir, int nv) {if (l > ir || r < il) return;if (il <= l && r <= ir) return void(v = lazy = nv);propagate();left->update(il, ir, nv);right->update(il, ir, nv);}inline int query (int x) {if (l > x || r < x) return 0;if (l == r && l == x) return v;propagate();return max(left->query(x), right->query(x));}};struct square {int x1,y1,x2,y2;} a [maxn];struct event {int x;int id;int type;bool operator < (const event& oth) {if (x != oth.x) return x < oth.x;return type < oth.type;}};struct point {int x;int y;int color;} b[maxn];vector <event> ev;int n, m;set <int> *dfs (int u){set <int> *pt = new set <int>;if (u > n) {pt->insert(b[u - n].color);return pt;}for (int v: ad[u]) {set <int> *now = dfs(v);if (now->size() > pt->size()) swap(now, pt);for (int j: *now) pt->insert(j);}rs[u] = pt->size();return pt;}int main() {cin >> n >> m;node* sgt = new node (1, 1e9, 0);for (int i = 1; i <= n; i++){cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;ev.push_back({a[i].x1, i, 1});ev.push_back({a[i].x2, i, 3});}for (int i = 1; i <= m; i++){cin >> b[i].x >> b[i].y >> b[i].color;ev.push_back({b[i].x, i, 2}); }sort(ev.begin(), ev.end());for (auto [x, id, type]: ev) {if (type == 1) {dad[id] = sgt->query(a[id].y2);ad[dad[id]].push_back(id);sgt->update(a[id].y1, a[id].y2, id);}if (type == 2) {dad[id + n] = sgt->query(b[id].y);ad[dad[id + n]].push_back(id + n);}if (type == 3) {sgt->update(a[id].y1, a[id].y2, dad[id]);}}dfs(0);for (int i = 1; i <= n; i++){cout << rs[i] << "\n";}delete sgt; return 0;}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
195 ms |
80956 KB |
Output is correct |
| 2 |
Correct |
197 ms |
81812 KB |
Output is correct |
| 3 |
Correct |
4 ms |
9684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
227 ms |
85100 KB |
Output is correct |
| 2 |
Correct |
233 ms |
85488 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
371 ms |
135632 KB |
Output is correct |
| 2 |
Correct |
383 ms |
128388 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
613 ms |
204036 KB |
Output is correct |
| 2 |
Correct |
610 ms |
187972 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
625 ms |
200784 KB |
Output is correct |
| 2 |
Correct |
632 ms |
190292 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9684 KB |
Output is correct |
