結果

問題 No.686 Uncertain LIS
ユーザー CZS_AK_IOI2025
提出日時 2025-03-05 22:09:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,372 bytes
コンパイル時間 1,786 ms
コンパイル使用メモリ 165,168 KB
実行使用メモリ 13,704 KB
最終ジャッジ日時 2025-03-05 22:09:10
合計ジャッジ時間 6,065 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define maxn 100005
#define ull unsigned __int128
using namespace std;
const int block=127;
int n,L[maxn],R[maxn],ans,blo[maxn],id[maxn],blol[maxn],blor[maxn];
ull dp[maxn],czs[130];
signed main(){
    // freopen("lis.in","r",stdin);
    // freopen("lis.out","w",stdout);
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;for(int i=1;i<=n;++i)cin>>L[i]>>R[i];
    memset(blol,-1,sizeof blol);
    for(int i=0;i<=100000;++i){
        blo[i]=i/(block);
        id[i]=i%(block);
        if(blol[blo[i]]==-1)blol[blo[i]]=i;
        blor[blo[i]]=i;
    }
    czs[0]=1;for(int i=1;i<=127;++i)czs[i]=czs[i-1]*2;
    dp[blo[0]]=czs[id[0]];
    for(int i=1;i<=n;++i){
        bool ntt=1;
        for(int j=R[i];j<=blor[blo[R[i]]];++j)if(dp[blo[R[i]]]&czs[id[j]]){dp[blo[j]]-=czs[id[j]];ntt=0;break;}
        if(ntt){
            for(int k=blo[R[i]]+1;k<=blo[100000];++k){
                if(dp[k]>0){
                    for(int q=0;q<=block;++q){
                        if(dp[k]&czs[q]){
                            dp[k]-=czs[q];
                            break;
                        }
                    }
                    break;
                }
            }
        }
        if(blo[L[i]]==blo[R[i]-1]){
            ull res=0;
            for(int j=L[i];j<=R[i]-1;++j)if(dp[blo[L[i]]]&czs[id[j]])res+=czs[id[j]];
            dp[blo[L[i]]]-=res;
            dp[blo[L[i]]]|=(res*2);
            dp[blo[L[i]]]|=czs[id[L[i]]];
            if(res&czs[block])dp[blo[L[i]]+1]|=1;
            continue;
        }
        ull res=0;
        for(int j=blol[R[i]-1];j<=R[i]-1;++j)if(dp[blo[R[i]-1]]&czs[id[j]])res+=czs[id[j]];
        dp[blo[R[i]-1]]-=res;dp[blo[R[i]-1]]|=(res*2);
        if(res&czs[block])dp[blo[R[i]-1]+1]|=1;
        for(int j=blo[R[i]-1]-1;j>=blo[L[i]]+1;--j){
            if(dp[j]&czs[block])dp[j+1]|=1;
            dp[j]*=2;
        }
        res=0;
        for(int j=L[i];j<=blor[blo[L[i]]];++j)if(dp[blo[L[i]]]&czs[id[j]])res+=czs[id[j]];
        dp[blo[L[i]]]-=res;dp[blo[L[i]]]|=(res*2);
        if(res&czs[block])dp[blo[L[i]]+1]|=1;
        dp[blo[L[i]]]|=czs[id[L[i]]];
    }
    for(int i=blo[0];i<blo[100000];++i){
        while(dp[i]){
            if(dp[i]&1)++ans;
            dp[i]>>=1;
        }
    }
    for(int i=0;i<=id[100000];++i)if(dp[blo[100000]]&czs[i])++ans;
    cout<<ans-1;
    return 0;
}
0