This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define vec vector
#define ins push_back
#define lc id<<1
#define rc id<<1|1
const int nax = 5e5;
void read(string name="") {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (name.size()) {
freopen((name + ".inp").c_str(), "r", stdin);
freopen((name + ".out").c_str(), "w", stdout);
}
}
struct tournament_tree {
int n;
vec<int> sgt, done;
void init(int _n) {
n = _n;
sgt = vec<int>(n*4+1);
done = vec<int>(n*4+1, 1);
}
void app(int id) {
if (done[id]) return;
sgt[lc] = sgt[id];
sgt[rc] = sgt[id];
done[lc] = done[rc] = 0;
done[id] = 1;
}
void add(int id, int lb, int rb, int l, int r, int val) {
if (l <= lb && rb <= r) {
sgt[id] = val;
done[id] = 0;
return;
} else if (rb < l || lb > r)
return;
app(id);
int mb = (lb + rb) >> 1;
add(lc, lb, mb, l, r, val);
add(rc, mb+1, rb, l, r, val);
}
int query(int id, int lb, int rb, int i) {
if (lb == rb) return sgt[id];
// if (i == 2) cout << lb << " " << rb << " " << sgt[id] << "\n";
app(id);
int mb = (lb + rb) >> 1;
if (i <= mb) return query(lc, lb, mb, i);
return query(rc, mb+1, rb, i);
}
void add(int l, int r, int val) {
add(1, 1, n, l, r, val);
}
int query(int i) {
return query(1, 1, n, i);
}
} sgt;
struct event {
int x, u, v, idx;
event(int _x=0, int _u=0, int _v=0, int _idx=0) : x(_x), u(_u), v(_v), idx(_idx) {}
bool operator<(const event b) const {
if (x == b.x) {
if (idx < 0) return 0;
if (b.idx < 0) return 1;
return v < b.v;
}
return x < b.x;
}
};
struct rect {
int u, v, p, q;
rect(int _u=0, int _v=0, int _p=0, int _q=0) : u(_u), v(_v), p(_p), q(_q) {}
};
struct ball {
int u, v, k;
ball(int _u=0, int _v=0, int _k=0) : u(_u), v(_v), k(_k) {}
};
int n, m, pa[nax], pb[nax], ans[nax];
rect a[nax];
ball b[nax];
set<int> col[nax];
vec<event> evts;
vec<int> zip, tree[nax];
// initialize
int pos(int val) {
return upper_bound(zip.begin(), zip.end(), val) - zip.begin();
}
void input() {
cin >> n >> m;
for(int i=1; i<=n; ++i) {
cin >> a[i].u >> a[i].v >> a[i].p >> a[i].q;
zip.ins(a[i].u);
zip.ins(a[i].v);
zip.ins(a[i].p);
zip.ins(a[i].q);
}
for(int i=1; i<=m; ++i) {
cin >> b[i].u >> b[i].v >> b[i].k;
zip.ins(b[i].u);
zip.ins(b[i].v);
}
sort(zip.begin(), zip.end());
zip.erase(unique(zip.begin(), zip.end()), zip.end());
sgt.init(zip.size());
for(int i=1; i<=n; ++i) {
a[i].u = pos(a[i].u);
a[i].v = pos(a[i].v);
a[i].p = pos(a[i].p);
a[i].q = pos(a[i].q);
}
for(int i=1; i<=m; ++i) {
b[i].u = pos(b[i].u);
b[i].v = pos(b[i].v);
}
}
void sweep() {
for(int i=1; i<=n; ++i) {
evts.ins(event(a[i].u, a[i].v, a[i].q, i));
evts.ins(event(a[i].p, a[i].v, a[i].q, -i));
}
for(int i=1; i<=m; ++i) {
evts.ins(event(b[i].u, b[i].v, nax, i));
}
sort(evts.begin(), evts.end());
for(int i=0; i<evts.size(); ++i) {
auto tmp = evts[i];
if (tmp.v == nax) {
pb[tmp.idx] = sgt.query(tmp.u);
col[pb[tmp.idx]].insert(b[tmp.idx].k);
continue;
}
if (tmp.idx < 0) sgt.add(tmp.u, tmp.v, pa[-tmp.idx]);
else {
pa[tmp.idx] = sgt.query(tmp.u);
tree[pa[tmp.idx]].ins(tmp.idx);
sgt.add(tmp.u, tmp.v, tmp.idx);
}
}
}
void dfs(int u, int p) {
for(int v : tree[u]) {
dfs(v, u);
if (col[u].size() < col[v].size())
swap(col[u], col[v]);
for(int x : col[v])
col[u].insert(x);
}
ans[u] = col[u].size();
}
void question() {
dfs(0, 0);
for(int i=1; i<=n; ++i)
cout << ans[i] << "\n";
}
int main() {
read("");
input();
sweep();
question();
return 0;
}
Compilation message (stderr)
plahte.cpp: In function 'void sweep()':
plahte.cpp:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for(int i=0; i<evts.size(); ++i) {
| ~^~~~~~~~~~~~
plahte.cpp: In function 'void read(std::string)':
plahte.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
17 | freopen((name + ".inp").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | freopen((name + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |