[HOJ] 234 - Convention

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<set>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define N 200005
struct P{
    int x,y;
    friend bool operator < (P a,P b){
        return a.y>b.y;
    }
}s[N];
struct T{
    int L,R,cnt;
    friend bool operator < (T a,T b){
        return a.R<b.R;
    }
};
set<T> _set;
set<T>::iterator k;
priority_queue<P> que;
vector<int> vec;
map<int,int> ma;
int dp[N*2][20];
int main(){
    int n,i,j,m=0,tmp,x,ans;
    memset(dp,-1,sizeof(dp));
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d",&s[i].x,&s[i].y);
        vec.push_back(s[i].x);
        vec.push_back(s[i].y);
    }
    sort(vec.begin(),vec.end());
    int add=0;
    for(i=0;i<vec.size();i++){
        if(ma.find(vec[i])==ma.end())
            ma[vec[i]]=add++;
    }
    for(i=0;i<n;i++){
        s[i].x=ma[s[i].x];
        s[i].y=ma[s[i].y];
        m=max(m,s[i].x);
        m=max(m,s[i].y);
        que.push(s[i]);
    }
    for(i=0;i<=m;i++){
        while(que.size() && que.top().x<i) que.pop();
        if(que.size()){
            dp[i][0]=que.top().y;
        }
    }
    /*for(i=0;i<=m;i++)
        printf("%d ",dp[i][0]);
    puts("");*/
    for(j=1;j<20;j++){
        for(i=0;i<=m;i++){
            tmp=dp[i][j-1]+1;
            if(tmp){
                dp[i][j]=dp[tmp][j-1];
            }

        }
    }
    x=0,ans=0;
    for(i=19;i>=0;i--){
        if(dp[x][i]!=-1){
            ans+=1<<i;
            x=dp[x][i]+1;
        }
    }
    //ans=7;
    printf("%d\n",ans);
    _set.insert((T){0,m,ans});
    for(i=0;i<n;i++){
        k=_set.lower_bound((T){0,s[i].y,0});
        if(k==_set.end() || (*k).L>s[i].x) continue;
        int addL=0,addR=0;
        if((*k).L!=s[i].x){
            x=(*k).L;
            for(j=19;j>=0;j--){
                if(dp[x][j]!=-1 && dp[x][j]<s[i].x){
                    addL+=1<<j;
                    x=dp[x][j]+1;
                }
            }
        }
        if((*k).R!=s[i].y){
            x=s[i].y+1;
            for(j=19;j>=0;j--){
                if(dp[x][j]!=-1 && dp[x][j]<=(*k).R){
                    addR+=1<<j;
                    x=dp[x][j]+1;
                }
            }
        }
        if(addL+1+addR!=(*k).cnt) continue;
        printf("%d ",i+1);
        T in=(*k);
        _set.erase(k);
        if(addL) _set.insert((T){in.L,s[i].x-1,addL});
        if(addR) _set.insert((T){s[i].y+1,in.R,addR});
    }

}