Submission #868982

#	Time	Username	Problem	Language	Result	Execution time	Memory
868982		ofrankel	Sweeping (JOI20_sweeping)	C++17	12 / 100	18181 ms	2094504 KiB

sweeping

#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[30000000];
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;
}

Compilation message (stderr)

sweeping.cpp: In function 'UNI* uni(UNI*, UNI*)':
sweeping.cpp:68:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   68 |     if(first==NULL)return second;if(second==NULL)return first;
      |     ^~
sweeping.cpp:68:34: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   68 |     if(first==NULL)return second;if(second==NULL)return first;
      |                                  ^~

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 11 / 11
• Subtask 4: 0 / 53
• Subtask 5: 0 / 25