結果

問題 No.686 Uncertain LIS
コンテスト
ユーザー CZS_AK_IOI2025
提出日時 2025-03-05 20:32:53
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,518 bytes
コンパイル時間 1,557 ms
コンパイル使用メモリ 162,120 KB
実行使用メモリ 8,612 KB
最終ジャッジ日時 2025-03-05 20:33:27
合計ジャッジ時間 4,873 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

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