#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
using namespace std;
struct Rect{
int dx,dy,ux,uy,id;
Rect(int a,int b,int c,int d,int e){
dx=a,dy=b,ux=c,uy=d,id=e;
}
};
struct Ball{
int x,y,color,id;
Ball(int a,int b,int c,int d){
x=a,y=b,color=c,id=d;
}
};
vector<Rect> arr;
vector<Ball> shot;
vector<int> Xl;
map<int,int>ptr;
vector<int>seg;
set<int> data[100000];
vector<int> indeg(100000,0);
vector<int>adj[100000];
vector<int> ans(100000,0);
int S,ind=0;
struct W{
int w,id;
W(int a,int b){
w=a,id=b;
}
bool operator<(W& A){
int x,X;
if(w)x=arr[id].ux;
else x=shot[id].x;
if(A.w)X=arr[A.id].ux;
else X=shot[A.id].x;
return x<X||(x==X&&w<A.w);
}
};
vector<W>X;
bool sort_by_dx(int a,int b){
return arr[a].dx<arr[b].dx;
}
void swap(map<int,int>& data,int w,int q){
int e=data[w];
data.erase(w);
data[q]=e;
}
int get(int a,int b){
if(a==-1)return b;
if(b==-1)return a;
if(arr[a].uy<arr[b].uy)return b;
else return a;
}
void build(){
S=(1<<(int)ceil(log2(seg.size())));
int l=S-seg.size();
for(int i=0;i<l;i++)seg.pb(-1);
reverse(all(seg));
for(int i=1;i<seg.size();i+=2){
seg.pb(get(seg[i],seg[i-1]));
}
seg.pb(-1);
reverse(all(seg));
}
void update(int j){
while(j>0){
seg[j]=get(seg[j*2],seg[j*2+1]);
j/=2;
}
}
void add(int id){
int j=seg.size()-S+ptr[arr[id].dy];
seg[j]=id;
update(j/2);
}
void erase(int id){
int j=seg.size()-S+ptr[arr[id].dy];
seg[j]=-1;
update(j/2);
}
int find(int j,int key){
while(j*2<seg.size()){
if(seg[j*2+1]!=-1&&arr[seg[j*2+1]].uy>=key)j=j*2+1;
else if(seg[j*2]!=-1&&arr[seg[j*2]].uy>=key)j=j*2;
else return -1;
}
if(seg[j]!=-1&&arr[seg[j]].uy>=key)
return seg[j];
else return -1;
}
int query(int j,int a,int b,int x,int y,int key){
if(y<a||b<x)return -1;
if(a<=x&&y<=b){
return find(j,key);
}
int q=query(j*2+1,a,b,(x+y)/2+1,y,key);
int w=query(j*2,a,b,x,(x+y)/2,key);
if(q==-1)return w;
else return q;
}
void dfs(int x){
for(int i=0;i<adj[x].size();i++){
int y=adj[x][i];
dfs(y);
if(data[x].size()<data[y].size())swap(data[x],data[y]);
for(set<int>::iterator itr=data[y].begin();itr!=data[y].end();itr++)data[x].insert(*itr);
data[y].clear();
}
ans[x]=data[x].size();
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("q.gir","r",stdin);
// freopen("q.cik","w",stdout);
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
int a,b,c,d;
cin>>a>>b>>c>>d;
arr.pb(Rect(a,b,c,d,i));
Xl.pb(i);
X.pb(W(1,i));
ptr[b]=0;
}
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
shot.pb(Ball(a,b,c,i));
X.pb(W(0,i));
ptr[b]=0;
}
sort(all(Xl),sort_by_dx);
sort(all(X));
for(map<int,int>::iterator itr=ptr.begin();itr!=ptr.end();itr++){
itr->second=ind++;
}
seg.resize(ptr.size(),-1);
build();
ind=0;
for(int i=0;i<n;i++){
int id=Xl[i];
while(ind<X.size()){
int w=X[ind].w,d=X[ind].id;
///erasing part
if(w){
if(arr[d].ux<arr[id].dx){
erase(d);
}
else break;
}
///query part
else{
if(shot[d].x<arr[id].dx){
int q=query(1,0,ptr[shot[d].y],0,S-1,shot[d].y);
if(q!=-1){
data[q].insert(shot[d].color);
}
}
else break;
}
ind++;
}
int q=query(1,0,ptr[arr[id].dy],0,S-1,arr[id].uy);
add(id);
if(q!=-1){
adj[q].pb(id);
indeg[id]++;
}
}
while(ind<X.size()){
int w=X[ind].w,d=X[ind].id;
if(w){
erase(d);
}
else{
int q=query(1,0,ptr[shot[d].y],0,S-1,shot[d].y);
if(q!=-1){
data[q].insert(shot[d].color);
}
}
ind++;
}
for(int i=0;i<n;i++){
if(indeg[i]==0){
dfs(i);
}
}
for(int i=0;i<n;i++)cout<<ans[i]<<"\n";
}
Compilation message
plahte.cpp: In function 'void build()':
plahte.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<seg.size();i+=2){
~^~~~~~~~~~~
plahte.cpp: In function 'int find(int, int)':
plahte.cpp:89:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j*2<seg.size()){
~~~^~~~~~~~~~~
plahte.cpp: In function 'void dfs(int)':
plahte.cpp:109:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<adj[x].size();i++){
~^~~~~~~~~~~~~~
plahte.cpp: In function 'int32_t main()':
plahte.cpp:150:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<X.size()){
~~~^~~~~~~~~
plahte.cpp:178:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind<X.size()){
~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
15756 KB |
Output is correct |
| 2 |
Correct |
168 ms |
15500 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
179 ms |
17936 KB |
Output is correct |
| 2 |
Correct |
171 ms |
16728 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
332 ms |
25668 KB |
Output is correct |
| 2 |
Correct |
320 ms |
21852 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
568 ms |
36640 KB |
Output is correct |
| 2 |
Correct |
569 ms |
30600 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
558 ms |
34692 KB |
Output is correct |
| 2 |
Correct |
522 ms |
29788 KB |
Output is correct |
| 3 |
Correct |
9 ms |
8184 KB |
Output is correct |
