| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 868980 | ofrankel | Sweeping (JOI20_sweeping) | C++17 | 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;
const int maxn=1500001;
struct UNI{
int x,y,ind;
set<pair<int,int>>*s;
int size;
bool isVertical;
UNI(int x_,int y_){x=x_;y=y_;s=NULL;size=0;ind=-1;}
UNI(int x_,int y_,int ind_){x=x_;y=y_;s=NULL;size=1;ind=ind_;isVertical=1;}
UNI* hafred(int g,int nXOrY);
pair<int,int> leorid (int g);
~UNI(){if(s)delete s;}
};
int n;
UNI* a[maxn];
vector<UNI*> sh (int x,int y);
void insert(int x,int y,UNI* cur);
void rem(int x,int y,UNI* cur);
vector <int> d;
vector<pair<int,int>>inpu;
UNI* UNI::hafred(int g,int nXOrY){
if(size==1){
if(isVertical)x=nXOrY;else y=nXOrY;
return this;
}
auto it1=s->begin();auto it2=s->rbegin();
bool measof=0;int count=0;
while(true){if(it1->first>g)break;if(it2->first<=g){measof=1;break;}count++;it1++;it2++;}
size-=count;
if(!measof){
UNI* toz=isVertical?new UNI(nXOrY,y):new UNI(x,nXOrY);
toz->size=count;
toz->isVertical=isVertical;
if(count==1){auto cur=*s->begin();s->erase(s->begin());a[cur.second]=toz;toz->ind=cur.second;
}
else{toz->s=new set<pair<int,int>>();
for(int i=0;count>i;++i){auto cur=*s->begin();if(i==0)toz->ind=cur.second;s->erase(s->begin());a[cur.second]=toz;toz->s->insert(cur);}}
if(isVertical)y=s->begin()->first;else x=s->begin()->first;
insert(x,y,this);
ind=s->begin()->second;
return toz;
}
else{
if(!count){if(isVertical)x=nXOrY;else y=nXOrY;return this;}
UNI* toz=isVertical?new UNI(x,0):new UNI(0,y);
if(isVertical)x=nXOrY;else y=nXOrY;
toz->size=count;
toz->isVertical=isVertical;
if(count==1){auto cur=*s->rbegin();s->erase(prev(s->end()));a[cur.second]=toz;toz->ind=cur.second;
if(isVertical)toz->y=cur.first;else toz->x=cur.first;insert(toz->x,toz->y,toz);if(size==1)ind=s->begin()->second;return this;
}
toz->s=new set<pair<int,int>>();
for(int i=0;count>i;++i){auto cur=*s->rbegin();s->erase(prev(s->end()));a[cur.second]=toz;toz->s->insert(cur);toz->ind=cur.second;}
if(isVertical)toz->y=toz->s->begin()->first;else toz->x=toz->s->begin()->first;insert(toz->x,toz->y,toz);return this;
}
}
pair<int,int> UNI::leorid (int g){
if(size==1){if(isVertical)return {x,ind};else return {y,ind};}
int cur=s->begin()->second;s->erase(s->begin());size--;
while(s->size()&&s->begin()->first<=g){int cur2=s->begin()->second;s->erase(s->begin());d[cur]=cur2;cur=cur2;size--;}
if(s->size())ind=s->begin()->second;
if(size){if(isVertical)y=s->begin()->first;else x=s->begin()->first;}
if(size) insert(x,y,this);
if(isVertical)return {x,cur};else return {y,cur};
}
UNI* uni(UNI* first,UNI* second){
if(first==NULL)return second;if(second==NULL)return first;
if(first->size<second->size)swap(first,second);
if(first->s==NULL){first->s=new set<pair<int,int>>({{first->isVertical?first->y:first->x,first->ind}});}
if(second->size>1)for(pair<int,int> cur:*(second->s)){a[cur.second]=first;first->s->insert(cur);}
else {first->s->insert({second->isVertical?second->y:second->x,second->ind});a[second->ind]=first;}
first->size+=second->size;
if(first->isVertical)first->y=first->s->begin()->first;
else first->x=first->s->begin()->first;
first->ind=first->s->begin()->second;
delete second;
return first;
}
void meuzan(int y){
UNI* st=NULL;
for(auto curr:sh(n-y-1,y)){
auto cur=curr;
if(cur->isVertical){
cur=cur->hafred(y,n-y);
st=uni(cur,st);
}
else{
auto cc=cur->leorid(n-y);
inpu[cc.second]={n-y,cur->y};
if(st==NULL){st=new UNI(n-y,cc.first);st->isVertical=true;st->ind=cc.second;st->size=1;a[cc.second]=st;continue;}
if(st->s==NULL){st->s=new set<pair<int,int>>({{st->y,st->ind}});
if(st->y>cc.first)st->ind=cc.second;}
st->s->insert({cc.first,cc.second});
st->y=min(st->y,cc.first);
st->size++;
a[cc.second]=st;
}
}
if(st!=NULL)insert(st->x,st->y,st);
}
void myfunc(){}
void meunach(int x){
UNI* st=NULL;
for(auto curr:sh(x,n-x-1)){
auto cur=curr;
if(!cur->isVertical){
cur=cur->hafred(x,n-x);
st=uni(cur,st);
}
else{
auto cc=cur->leorid(n-x);
inpu[cc.second]={cur->x,n-x};
if(st==NULL){st=new UNI(cc.first,n-x);st->isVertical=false;st->ind=cc.second;st->size=1;a[cc.second]=st;continue;}
if(st->s==NULL){st->s=new set<pair<int,int>>({{st->x,st->ind}});
if(st->x>cc.first)st->ind=cc.second;}
st->s->insert({cc.first,cc.second});
st->x=min(st->x,cc.first);
st->size++;
a[cc.second]=st;
}
}
if(st!=NULL)insert(st->x,st->y,st);
}
set<pair<int,int>>SEG;
set<pair<pair<int,int>,UNI*>>SEG2[50000000];
int indSEG=0;
void insert(int x,int y,UNI* cur){
int ox=x;
x++;
while(x<=n+1){
auto it=SEG.lower_bound({x,0});
if(it==SEG.end()||it->first!=x)it=SEG.insert({x,indSEG++}).first;
SEG2[it->second].insert({{y,ox},cur});
x+=x&(-x);
}
}
void rem(int x,int y,UNI* cur){
int ox=x;
x++;
while(x<=n+1){
auto it=SEG.lower_bound({x,0});
SEG2[it->second].erase({{y,ox},cur});
x+=x&(-x);
}
}
vector<UNI*> sh (int x,int y){
x++;
vector<UNI*>toz;
while(x>0){
auto it=SEG.lower_bound({x,0});
if(it!=SEG.end()&&it->first==x)
while(SEG2[it->second].size()&&SEG2[it->second].begin()->first.first<=y){
auto it2=SEG2[it->second].begin();
toz.push_back(it2->second);
rem(it2->first.second,it2->first.first,it2->second);
}
x-=x&(-x);
}
return toz;
}
int find(int x){if(d[x]==x)return x;return d[x]=find(d[x]);}
pair<int,int>calc(int x){
x=find(x);
int x1=inpu[x].first;int y1=inpu[x].second;
x1=max(x1,a[x]->x);
y1=max(y1,a[x]->y);
return {x1,y1};
}
int main()
{
int m,q;cin>>n>>m>>q;
int x,y;for(int i=0;m>i;++i){cin>>x>>y;a[i]=new UNI(x,y,i);insert(x,y,a[i]);d.push_back(i);inpu.push_back({x,y});}
int cind=m;
for(int i_=m;m+q>i_;++i_){
int t;cin>>t;
if(t==1){
cin>>x;x--;
auto toz=calc(x);
cout<<toz.first<<" "<<toz.second<<endl;
}
else if(t==2){
cin>>x;meuzan(x);
}
else if(t==3){cin>>x;meunach(x);}
else {cin>>x>>y;a[cind]=new UNI(x,y,cind);insert(x,y,a[cind]);d.push_back(cind);inpu.push_back({x,y});cind++;}
//for(int i=0;cind>i;++i){auto toz=calc(i);cout<<i+1<<": "<<toz.first<<", "<<toz.second<<" | ";}cout<<endl;
//if(i_>m+80)break;
//for(int i=0;cind>i;++i)if(a[find(i)]->size==1&&(a[find(i)]->y!=||))cout<<"hi "<<i_<<endl;
}
return 0;
}