結果
問題 |
No.686 Uncertain LIS
|
ユーザー |
|
提出日時 | 2025-03-05 22:27:13 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 297 ms / 2,000 ms |
コード長 | 844 bytes |
コンパイル時間 | 2,193 ms |
コンパイル使用メモリ | 172,100 KB |
実行使用メモリ | 8,608 KB |
最終ジャッジ日時 | 2025-03-05 22:27:20 |
合計ジャッジ時間 | 6,368 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; const int block=320; int n,res,a[block]; deque<int>q[block]; signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n; for(int i=0;i<block;++i)for(int j=0;j<block;++j)q[i].push_back(0); for(int i=0;i<n;++i){ int l,r; cin>>l>>r; int li=l/block,ri=r/block,b=1; for(int j=r%block;j<block;++j)if(q[ri][j]){ q[ri][j]=b=0; --a[ri]; break; } if(b&&ri!=block-1){ int I=ri+1; while(I<block&&!a[I])++I; if(I<block){ for(int j=0;j<block;++j)if(q[I][j]){ q[I][j]=b=0; --a[I]; break; } } } res+=b; q[ri].erase(q[ri].begin()+r%block); for(int j=li;j<ri;++j){ int t=q[j].back(); a[j]-=t; a[j+1]+=t; q[j].pop_back(); q[j+1].push_front(t); } q[li].insert(q[li].begin()+l%block,1); a[li]++; } cout<<res<<endl; }