結果

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

ソースコード

diff # 

#include<bits/stdc++.h>
#define maxn 100005
#define ull unsigned long long
using namespace std;
const ull block=62;
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(){
    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[j]]&czs[id[j]]){dp[blo[j]]^=czs[id[j]];ntt=0;break;}
        for(int j=id[100000]+1;j<=block;++j)
            if(dp[blo[100000]]&czs[j])
                dp[blo[100000]]^=czs[j];
        if(ntt){
            for(int k=blo[R[i]]+1;k<=blo[100000];++k){
                if(dp[k]){
                    for(int q=0;q<=block;++q){
                        if(dp[k]&czs[q]){
                            dp[k]-=czs[q];
                            break;
                        }
                    }
                    if(k==blo[100000])
                        for(int j=id[100000]+1;j<=block;++j)
                            if(dp[blo[100000]]&czs[j])
                                dp[blo[100000]]^=czs[j];
                    break;
                }
            }
        }
        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]>>=1;
            for(int jj=id[blor[j]]+1;jj<=block;++jj)
                if(dp[j]&czs[jj])
                    dp[j]^=czs[jj];
        }
        ull 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+czs[id[L[i]]];
        if(blo[L[i]]==blo[100000])
        for(int j=id[100000]+1;j<=block;++j)
        if(dp[blo[100000]]&czs[j])
        dp[blo[100000]]^=czs[j];
    }
    for(int i=blo[0];i<blo[100000];++i)ans+=__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