#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
struct Query{
int type;
int idx,x,y;
int l;
Query(){}
Query(int t,int i,int X,int Y):type(t),idx(i),x(X),y(Y),l(-1){}
Query(int t,int i,int L):type(t),idx(i),l(L),x(-1),y(-1){}
};
const int N=3000050;
pii ans[N];
int n,m,q;
int val[N],myc[N],tsz,rem[N];
vector<int> cmp[N];
int add(int i,int v){tsz++;val[tsz]=v;myc[i]=tsz;cmp[tsz]={i};return tsz;}
int mrg(int a,int b){
if(cmp[a].size()>cmp[b].size())swap(a,b);
for(int i:cmp[a]){
myc[i]=b;
cmp[b].pb(i);
}
cmp[a].clear();
return b;
}
void DNC(int l,int r,vector<Query> Qs){
int mid=l+r>>1;
int X=mid,Y=n-mid;
priority_queue<pii> xs,ys;
vector<Query> LQ,RQ;
for(Query qu:Qs){
if(qu.type==1){
int x=val[myc[qu.idx<<1]],y=val[myc[qu.idx<<1|1]];
if(rem[qu.idx]==1)RQ.pb(qu);
else if(rem[qu.idx]==2)LQ.pb(qu);
else ans[qu.l]={x,y};
}else if(qu.type==2){
if(qu.l<Y){
RQ.pb(qu);
while(ys.size()&&-ys.top().first<=qu.l){
int c=ys.top().second;
ys.pop();
for(int i:cmp[c])if(!rem[i/2]){
int x=n-qu.l,y=val[c];
RQ.pb(Query(4,i/2,x,y));
rem[i/2]=1;
}
}
}else{
int now=0;
while(xs.size()&&-xs.top().first<n-qu.l){
int tmp=xs.top().second;
xs.pop();
now=now?mrg(now,tmp):tmp;
}
if(now)val[now]=n-qu.l,xs.push({-val[now],now});
LQ.pb(qu);
}
}else if(qu.type==3){
if(qu.l<X){
LQ.pb(qu);
while(xs.size()&&-xs.top().first<=qu.l){
int c=xs.top().second;
xs.pop();
for(int i:cmp[c])if(!rem[i/2]){
int x=val[myc[i^1]],y=n-qu.l;
LQ.pb(Query(4,i/2,x,y));
rem[i/2]=2;
}
}
}else{
int now=0;
while(ys.size()&&-ys.top().first<n-qu.l){
int tmp=ys.top().second;
ys.pop();
now=now?mrg(now,tmp):tmp;
}
if(now)val[now]=n-qu.l,ys.push({-val[now],now});
RQ.pb(qu);
}
}else{
if(qu.x>X)rem[qu.idx]=1,RQ.pb(qu);
else if(qu.y>Y)rem[qu.idx]=2,LQ.pb(qu);
else{
rem[qu.idx]=0;
xs.push({-qu.x,add(qu.idx<<1,qu.x)});
ys.push({-qu.y,add(qu.idx<<1|1,qu.y)});
}
}
}
if(l==r)return;
if(l+1==r)DNC(r,r,RQ);
else{
DNC(l,mid,LQ);
DNC(mid,r,RQ);
}
}
int main(){
scanf("%i %i %i",&n,&m,&q);
vector<Query> Qs;
for(int i=1,x,y;i<=m;i++){
scanf("%i %i",&x,&y);
Qs.pb(Query(4,i,x,y));
}
int z=0;
for(int i=1;i<=q;i++){
int t;scanf("%i",&t);
if(t==1){
int idx;scanf("%i",&idx);
Qs.pb(Query(1,idx,++z));
}else if(t==2||t==3){
int l;scanf("%i",&l);
Qs.pb(Query(t,-1,l));
}else{
int x,y;scanf("%i %i",&x,&y);
Qs.pb(Query(4,++m,x,y));
}
}
DNC(0,n,Qs);
for(int i=1;i<=z;i++)printf("%i %i\n",ans[i].first,ans[i].second);
return 0;
}
Compilation message
sweeping.cpp: In constructor 'Query::Query(int, int, int)':
sweeping.cpp:8:6: warning: 'Query::l' will be initialized after [-Wreorder]
8 | int l;
| ^
sweeping.cpp:7:10: warning: 'int Query::x' [-Wreorder]
7 | int idx,x,y;
| ^
sweeping.cpp:11:2: warning: when initialized here [-Wreorder]
11 | Query(int t,int i,int L):type(t),idx(i),l(L),x(-1),y(-1){}
| ^~~~~
sweeping.cpp: In function 'void DNC(int, int, std::vector<Query>)':
sweeping.cpp:29:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid=l+r>>1;
| ~^~
sweeping.cpp: In function 'int main()':
sweeping.cpp:101:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
101 | scanf("%i %i %i",&n,&m,&q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
sweeping.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
104 | scanf("%i %i",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
sweeping.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
109 | int t;scanf("%i",&t);
| ~~~~~^~~~~~~~~
sweeping.cpp:111:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
111 | int idx;scanf("%i",&idx);
| ~~~~~^~~~~~~~~~~
sweeping.cpp:114:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
114 | int l;scanf("%i",&l);
| ~~~~~^~~~~~~~~
sweeping.cpp:117:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
117 | int x,y;scanf("%i %i",&x,&y);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18053 ms |
74384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18089 ms |
305448 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18095 ms |
322768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18095 ms |
322768 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18053 ms |
74384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
