結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0