結果

問題 No.686 Uncertain LIS
ユーザー CZS_AK_IOI2025
提出日時 2025-03-05 21:29:26
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,497 bytes
コンパイル時間 1,924 ms
コンパイル使用メモリ 164,132 KB
実行使用メモリ 8,608 KB
最終ジャッジ日時 2025-03-05 21:29:33
合計ジャッジ時間 6,240 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 WA * 5 TLE * 1 -- * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define maxn 100005
#define int long long
#define ull unsigned long long
using namespace std;
const ull block=63;
int n,L[maxn],R[maxn],ans,blo[maxn],id[maxn],blol[maxn],blor[maxn];
bitset<maxn>f;ull dp[maxn],czs[66],mod;
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]=1ull;for(int i=1;i<=63;++i)czs[i]=czs[i-1]*2ull;
    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]){
                    for(int q=0;q<=63;++q){
                        if(dp[k]&czs[q]){
                            dp[k]-=czs[q];
                            break;
                        }
                    }
                    break;
                }
            }
        }
        if(blo[L[i]]==blo[R[i]-1]){
            ull res=0ull;
            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*2ull);
            dp[blo[L[i]]]|=czs[id[L[i]]];
            if(res&czs[block])dp[blo[L[i]]+1]|=1;
            continue;
        }
        ull res=0ull;
        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*2ull);
        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]*=2ull;
            for(int jj=id[blor[j]]+1;jj<=63;++jj)
                if(dp[j]&czs[jj])
                    dp[j]-=czs[jj];
        }
        res=0ull;
        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*2ull);
        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)ans+=1ll*__builtin_popcountll(dp[i]);
    for(int i=0;i<=id[100000];++i)if(dp[blo[100000]]&czs[i])++ans;
    cout<<ans-1;
    return 0;
}
0