oj.uz

답안 #613736

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
613736 2022-07-30T09:59:22 Z Vanilla Plahte (COCI17_plahte) C++17
160 / 160
 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;}

Subtask #1
32.0 / 32.0

# 결과 실행 시간 메모리 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

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 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

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 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

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 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

Subtask #5
32.0 / 32.0

# 결과 실행 시간 메모리 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