#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long int
#define oo 1e9
#define pii pair<int, int>
struct rect{
int x1, y1, x2, y2;
};
const int MAX = 8e4 + 8;
int n, m;
rect rects[MAX];
pii paintballs[MAX];
int c[MAX];
int tree[int(1e6)];
void update(int pos, int val){
for (int i = pos; i < 1e6; i += (-i) & i){
tree[i] += val;
}
}
int ask(int l, int r){
if(l != 1) ask(1, r) - ask(1, l - 1);
int res = 0;
for (int i = r; i > 0; i -= (-i) & i){
res += tree[i];
}
return res;
}
void input(){
cin >> n >> m;
map<int, int> mp;
for (int i = 1; i <= n; i++)
{
cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2;
mp[rects[i].y1];
mp[rects[i].y2];
}
for (int i = 1; i <= m; i++)
{
cin >> paintballs[i].first >> paintballs[i].second >> c[i];
mp[paintballs[i].second];
}
int c = 1;
for(auto& p:mp){
p.second = c++;
}
for (int i = 1; i <= n; i++)
{
rects[i].y1 = mp[rects[i].y1];
rects[i].y2 = mp[rects[i].y2];
}
for (int i = 1; i <= m; i++)
{
paintballs[i].second = mp[paintballs[i].second];
}
}
vector<array<int, 3>> events;
int par[MAX << 1];
vector<int> g[MAX << 1];
set<int> sub[MAX << 1];
int ans[MAX << 1];
void dfs(int node){
for(int to:g[node]){
dfs(to);
if(sub[node].size() < sub[to].size()){
swap(sub[node], sub[to]);
}
}
for(int to:g[node]){
for(int a:sub[to]){
sub[node].insert(a);
}
}
if(node > n){
sub[node].insert(c[node - n]);
}
ans[node] = sub[node].size();
}
int main(){
input();
for (int i = 1; i <= m; i++)
{
events.push_back({paintballs[i].first, 1, i});
}
for (int i = 1; i <= n; i++)
{
events.push_back({rects[i].x1, 0, i});
events.push_back({rects[i].x2, 2, i});
}
sort(events.begin(), events.end());
for(auto e : events){
if(e[1] == 1){
par[e[2] + n] = ask(1, paintballs[e[2]].second);
g[par[e[2] + n]].push_back(e[2] + n);
}
else if(e[1] == 0){
par[e[2]] = ask(1, rects[e[2]].y1);
g[par[e[2]]].push_back(e[2]);
update(rects[e[2]].y1, e[2] - par[e[2]]);
update(rects[e[2]].y2 + 1, -(e[2] - par[e[2]]));
}
else{
update(rects[e[2]].y1, -(e[2] - par[e[2]]));
update(rects[e[2]].y2 + 1, e[2] - par[e[2]]);
}
}
dfs(0);
for(int i = 1; i <= n; ++i){
cout << ans[i] << '\n';
}
}
Compilation message
plahte.cpp: In function 'int ask(int, int)':
plahte.cpp:33:26: warning: value computed is not used [-Wunused-value]
33 | if(l != 1) ask(1, r) - ask(1, l - 1);
| ~~~~~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
19864 KB |
Output is correct |
| 2 |
Correct |
143 ms |
20300 KB |
Output is correct |
| 3 |
Correct |
7 ms |
11600 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
166 ms |
21708 KB |
Output is correct |
| 2 |
Correct |
184 ms |
20932 KB |
Output is correct |
| 3 |
Correct |
8 ms |
11604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
288 ms |
29216 KB |
Output is correct |
| 2 |
Correct |
318 ms |
25832 KB |
Output is correct |
| 3 |
Correct |
7 ms |
11604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
545 ms |
39652 KB |
Output is correct |
| 2 |
Correct |
547 ms |
35320 KB |
Output is correct |
| 3 |
Correct |
7 ms |
11604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
496 ms |
37784 KB |
Output is correct |
| 2 |
Correct |
461 ms |
34536 KB |
Output is correct |
| 3 |
Correct |
9 ms |
11664 KB |
Output is correct |
