| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 290131 | TadijaSebez | Sweeping (JOI20_sweeping) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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=1500050;
const int M=2*N*30;
pii ans[N];
int n,m,q;
int val[M],myc[N*2],tsz,rem[N];
vector<int> cmp[M];
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){
if(Qs.empty())return;
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[c],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;
}