Submission #3644282

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define repl(i,a,b) for(int i=(int)(a);(i)<(int)(b);++(i))
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x<<"="<<x<<endl
#define fi first
#define se second


typedef pair<int,int> P;

int N,M;
vector<P> ps;
int nxt[1000010][21];

int main(){
    memset(nxt,-1,sizeof(nxt));
    cin>>N>>M;
    rep(i,N){
        int a,b;
        cin>>a>>b;
        if(a>b){
            b+=M;
        }
        ps.push_back(P(a,b));
        ps.push_back(P(a+M,b+M));
    }
    sort(all(ps),[=](const P& a,const P& b){ return a.fi > b.fi; });

    {
        set<int> st;
        int i = 0;
        for (int j = M * 2 - 1; j >= 0; j--) {
            while (i<(int)ps.size()&&ps[i].fi == j) {
                st.insert(ps[i].se);
                i++;
            }
            if (st.size() == 0) nxt[j][0] = -1;
            else nxt[j][0] = *st.begin();
        }
    }

    rep(k,20){
        rep(i,M*2){
            if(nxt[i][k]==-1)nxt[i][k+1]=-1;
            else nxt[i][k+1]=nxt[nxt[i][k]][k];
        }
    }

    int res=1;
    rep(i,N*2){
        int a=ps[i].fi,b=ps[i].se;
        int lb=0,ub=N;
        while(ub-lb>1){
            int X=(ub+lb)/2;
            int idx=b;
            rep(k,21){
                if((X>>k)&1){
                    idx=nxt[idx][k];
                    if(idx==-1)break;
                }
            }
            if(idx!=-1&&idx<=a+M) lb=X;
            else ub=X;
        }
        res=max(res,lb+1);
    }
    cout<<res<<endl;

    return 0;
}

Submission Info

Judge Result