Submission #27696734

---

Source Code Expand

/**
 *    author:  gary
 *    created: 04.12.2021 19:52:07
**/
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define rep(a,b) for(int a=0;a<b;++a)
#define LL long long
#define PB push_back
#define POB pop_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
int fa[1000000+20];
int root(int x){
    return fa[x]=(fa[x]==x? x:root(fa[x]));
}
int id[1000000+20];
vector<int> v[1000000+20];
int pre[1000000+20];
bool vis[1000000+20];
int mn[1000000+20];
int main(){
    // freopen("c.in","r",stdin);
    // freopen("c.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    rb(i,0,n) fa[i]=i;
    vector<mp> seg;
    int m;
    cin>>m;
    rb(i,1,m){
        int l,r;
        cin>>l>>r;
        int A,B;
        A=root(r);
        B=root(l-1);
        fa[max(A,B)]=min(A,B);
    }
    rb(i,0,n) mn[i]=INF;
    rb(i,0,n) check_min(mn[root(i)],i);
    rb(i,0,n) id[i]=mn[root(i)],v[id[i]].PB(i);
    int tmp=0;
    unordered_set<int> se;
    for(int i=0;tmp!=n+1;i--){
        if(i==0){
            tmp+=v[0].size();
            for(auto it:v[0]){
                vis[it]=1;
                se.insert(it);
                pre[it]=0;
            }
            assert(!se.empty());
            continue;
        }
        unordered_set<int> nw;
        for(auto ite=se.begin();ite!=se.end();ite++){
            if(*ite!=0&&!vis[*ite-1]){
                nw.insert(id[*ite-1]);
            }
            if(*ite!=n&&!vis[*ite+1]){
                nw.insert(id[*ite+1]);
            }
        }
            assert(!nw.empty());
        se.clear();
        for(auto ite=nw.begin();ite!=nw.end();ite++){
            auto Tmp=v[*ite];
            tmp+=Tmp.size();
            for(auto it:Tmp){
                vis[it]=1;
                se.insert(it);
                pre[it]=i;
            }
        }
    }
    rb(i,1,n){
        if(pre[i]==pre[i-1]-1) cout<<0;
        else cout<<1;
    }
    return 0;
}

Submission Info

Judge Result