結果
問題 |
No.686 Uncertain LIS
|
ユーザー |
|
提出日時 | 2025-03-30 14:41:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 179 ms / 2,000 ms |
コード長 | 3,014 bytes |
コンパイル時間 | 2,777 ms |
コンパイル使用メモリ | 209,208 KB |
実行使用メモリ | 7,324 KB |
最終ジャッジ日時 | 2025-03-30 14:41:30 |
合計ジャッジ時間 | 7,894 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
ソースコード
#include<bits/stdc++.h> using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<48||ch>57){if(ch=='-')f=-1;ch=getchar();} while(ch>=48&&ch<=57)x=(x<<1)+(x<<3)+(ch&15),ch=getchar(); return x*f; } inline void write(int x) { if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x%10+48); return; } constexpr int Mx=1e5+4; mt19937_64 dg(time(0)); int root,tot; struct FHQ_Treap { int l,r,size,v,mkadd,key; FHQ_Treap(){v=l=r=size=0,key=-1,mkadd=0;} FHQ_Treap(int val){l=r=0,v=val,key=dg(),size=1,mkadd=0;} }tr[Mx]; inline int newnode(int val) { int id=++tot; tr[id]=FHQ_Treap(val); return id; } inline void combine(int rt){tr[rt].size=tr[tr[rt].l].size+tr[tr[rt].r].size+1;return;} inline void pushdown_add(int rt,int v) { tr[rt].v+=v; tr[rt].mkadd+=v; return; } inline void pushdown(int rt) { if(!tr[rt].mkadd)return; pushdown_add(tr[rt].l,tr[rt].mkadd); pushdown_add(tr[rt].r,tr[rt].mkadd); tr[rt].mkadd=0; return; } //inline void split_by_size(int rt,int val,int&l,int&r) //{ // if(!rt){l=r=0;return;} // pushdown(rt); // if(tr[tr[rt].l].size<val) // { // split_by_size(tr[l].r,val-tr[tr[rt].l].size-1,tr[l].r,r); // combine(l); // } // else // { // split_by_size(tr[r].l,val,l,tr[r].l); // combine(r); // } // return; //} inline void split_by_val(int rt,int val,int&l,int&r) { if(!rt){l=r=0;return;} pushdown(rt); if(tr[rt].v<val){l=rt;split_by_val(tr[rt].r,val,tr[rt].r,r);} else{r=rt;split_by_val(tr[rt].l,val,l,tr[rt].l);} combine(rt); return; } inline void split_by_size(int rt,int val,int&l,int&r) { if(!rt){l=r=0;return;} pushdown(rt); if(tr[tr[rt].l].size<val){l=rt;split_by_size(tr[rt].r,val-tr[tr[rt].l].size-1,tr[rt].r,r);} else{r=rt;split_by_size(tr[rt].l,val,l,tr[rt].l);} combine(rt); return; } inline int merge(int l,int r) { if(!l||!r)return l+r; if(tr[l].key<tr[r].key) { pushdown(l); tr[l].r=merge(tr[l].r,r); combine(l); return l; } else { pushdown(r); tr[r].l=merge(l,tr[r].l); combine(r); return r; } } inline void insert(int v) { int l,r; split_by_val(root,v,l,r); root=merge(l,merge(newnode(v),r)); return; } inline void destroy(int v) { int x,y,z; split_by_val(root,v,x,z); split_by_size(z,1,y,z); root=merge(x,z); return; } inline void add(int l,int r,int v) { int x,y,z; split_by_val(root,l,x,z); split_by_val(z,r,y,z); pushdown_add(y,v); root=merge(x,merge(y,z)); return; } inline int find_nxt(int v) { int x,y,z,res; split_by_val(root,v+1,x,z); split_by_size(z,1,y,z); if(!y)return 0; res=tr[y].v; root=merge(x,merge(y,z)); return res; } int main() { int n=read(); for(int i=1;i<=n;++i) { int l=read(),r=read(); if(i==1){insert(l);continue;} int x=find_nxt(r-1); add(l,r,1); if(x)destroy(x); insert(l); } write(tr[root].size); return 0; }