#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 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;
set<ar<int, 3>> s, s2;
vector<int> adj[mxN];
set<int> dp[mxN];
int check(int y) {
auto it=s.upper_bound({y});
if (it==s.begin())
return -1;
ar<int, 3> a=*(--it);
if (y<=a[1])
return a[2];
it=s2.lower_bound({y});
if (it==s.end())
return -1;
a=*it;
return y>=a[1]?a[2]:-1;
}
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];
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];
e.push_back({x, 2, i});
}
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=check(ys[i][0]);
if (x^-1) {
p[i]=x;
adj[p[i]].push_back(i);
}
s.insert({ys[i][0], ys[i][1], i});
s2.insert({ys[i][1], ys[i][0], i});
} else if (a[1]==2) {
int x=check(ball[i][0]);
if (x^-1)
dp[x].insert(ball[i][1]);
} else {
s.erase({ys[i][0], ys[i][1], i});
s2.erase({ys[i][1], ys[i][0], i});
}
}
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 |
Incorrect |
79 ms |
11172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
90 ms |
15544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
24120 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
298 ms |
34748 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
261 ms |
31048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
