이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 8e4 + 2;
vector <int> ad [maxn];
int dad [4 * maxn];
int rs [maxn];
set <int> stl [maxn * 4];
struct node {
int l, r, v;
int lazy = 0;
node* left = NULL;
node* right = NULL;
node(int _l, int _r, int _v): l(_l), r(_r), v(_v) {};
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 != 0){
left->v = left->lazy = right->v = right->lazy = lazy;
lazy = 0;
}
}
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);
}
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; // 1 -> start square, 2 -> point, 3-> end square
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;
void dfs (int u) {
if (u > n) {
stl[u].insert(b[u - n].color);
return;
}
for (int v: ad[u]) {
dfs(v);
if (stl[v] > stl[u]) swap(stl[u], stl[v]);
for (int i: stl[v]) stl[u].insert(i);
stl[v].clear();
}
rs[u] = stl[u].size();
return;
}
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; // plbm este memory leak
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |