#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
// just build a tree on the rectanges, and then a simple dfs to push the colors down
// the question is how do we build the tree, and how do we find the topmost rectangle that each shot hits
// idea: sweepline
// specifics: put all active rectangles in a set (maybe segtree tbh) and sweep
const int mxN=80000;
int n, m, p[mxN], ans[mxN];
ar<int, 2> ys[mxN], ball[mxN];
vector<ar<int, 3>> e;
vector<int> d, s[3*4*mxN], adj[mxN];
set<int> dp[mxN];
void upd(int ql, int qr, int x, int u=1, int l=0, int r=d.size()-1) {
if (l>qr||r<ql)
return;
if (ql<=l&&r<=qr) {
x^-1?s[u].push_back(x):s[u].pop_back();
return;
}
int mid=(l+r)/2;
upd(ql, qr, x, 2*u, l, mid);
upd(ql, qr, x, 2*u+1, mid+1, r);
}
int qry(int x, int u=1, int l=0, int r=d.size()-1) {
int cur=s[u].empty()?-1:s[u].back();
if (l==r)
return cur;
int mid=(l+r)/2;
int lo=x<=mid?qry(x, 2*u, l, mid):qry(x, 2*u+1, mid+1, r);
return lo^-1?lo:cur;
}
void dfs(int u) {
for (int v : adj[u]) {
dfs(v);
if (dp[v].size()>dp[u].size())
swap(dp[u], dp[v]);
for (const int& i : dp[v])
dp[u].insert(i);
set<int>().swap(dp[v]);
}
ans[u]=dp[u].size();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i=0; i<n; ++i) {
int a, b;
cin >> a >> ys[i][0] >> b >> ys[i][1];
d.push_back(ys[i][0]);
d.push_back(ys[i][1]);
e.push_back({a, 1, i});
e.push_back({b, 3, i});
}
for (int i=0; i<m; ++i) {
int x;
cin >> x >> ball[i][0] >> ball[i][1];
d.push_back(ball[i][0]);
e.push_back({x, 2, i});
}
sort(d.begin(), d.end());
d.resize(unique(d.begin(), d.end())-d.begin());
for (int i=0; i<n; ++i) {
ys[i][0]=lower_bound(d.begin(), d.end(), ys[i][0])-d.begin();
ys[i][1]=lower_bound(d.begin(), d.end(), ys[i][1])-d.begin();
}
for (int i=0; i<m; ++i)
ball[i][0]=lower_bound(d.begin(), d.end(), ball[i][0])-d.begin();
sort(e.begin(), e.end());
memset(p, -1, sizeof(p));
for (ar<int, 3> a : e) {
int i=a[2];
if (a[1]==1) {
int x=qry(ys[i][0]);
if (x^-1) {
p[i]=x;
adj[p[i]].push_back(i);
}
upd(ys[i][0], ys[i][1], i);
} else if (a[1]==2) {
int x=qry(ball[i][0]);
if (x^-1)
dp[x].insert(ball[i][1]);
} else {
upd(ys[i][0], ys[i][1], -1);
}
}
for (int i=0; i<n; ++i)
if (p[i]==-1)
dfs(i);
for (int i=0; i<n; ++i)
cout << ans[i] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
35288 KB |
Output is correct |
| 2 |
Correct |
119 ms |
35048 KB |
Output is correct |
| 3 |
Correct |
18 ms |
28748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
39120 KB |
Output is correct |
| 2 |
Correct |
145 ms |
37404 KB |
Output is correct |
| 3 |
Correct |
19 ms |
28852 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
253 ms |
47300 KB |
Output is correct |
| 2 |
Correct |
232 ms |
42108 KB |
Output is correct |
| 3 |
Correct |
17 ms |
28796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
433 ms |
57852 KB |
Output is correct |
| 2 |
Correct |
411 ms |
49208 KB |
Output is correct |
| 3 |
Correct |
18 ms |
28748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
425 ms |
54188 KB |
Output is correct |
| 2 |
Correct |
432 ms |
49152 KB |
Output is correct |
| 3 |
Correct |
18 ms |
28748 KB |
Output is correct |
