結果

問題 No.686 Uncertain LIS
コンテスト
ユーザー vjudge1
提出日時 2025-02-23 18:23:37
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 239 ms / 2,000 ms
コード長 1,934 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,555 ms
コンパイル使用メモリ 164,884 KB
実行使用メモリ 10,056 KB
最終ジャッジ日時 2025-02-23 18:23:51
合計ジャッジ時間 6,599 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:87:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
main.cpp:88:35: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   88 |         for(int i=1;i<=n;++i)scanf("%d%d",&l[i],&r[i]);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
mt19937 mt(13770618);
int tot=0;
struct apple{
	int ls,rs,zz,sz,hp;
}e[300005];
int lz[300005];
void update(int x){
	e[x].sz=e[e[x].ls].sz+e[e[x].rs].sz+1;
}
void pushdown(int x){
	if(!x||!lz[x])return;
	if(e[x].ls){
		e[e[x].ls].zz+=lz[x];
		lz[e[x].ls]+=lz[x];
	}
	if(e[x].rs){
		e[e[x].rs].zz+=lz[x];
		lz[e[x].rs]+=lz[x];
	}
	lz[x]=0;
}
int rt=0;
pair<int,int>split(int ys,int k){
	if(!ys)return make_pair(0,0);
	pushdown(ys);
	if(e[ys].zz<=k){
		auto pi=split(e[ys].rs,k);
		e[ys].rs=pi.first;
		update(ys);
		return make_pair(ys,pi.second);
	}
	auto pi=split(e[ys].ls,k);
	e[ys].ls=pi.second;
	update(ys);
	return make_pair(pi.first,ys);
}
int merg(int x,int y){
	if(!x)return y;
	if(!y)return x;
	pushdown(x);pushdown(y);
	if(e[x].hp<e[y].hp){
		e[x].rs=merg(e[x].rs,y);
		update(x);
		return x;
	}
	e[y].ls=merg(x,e[y].ls);
	update(y);
	return y;
}
void inser(int x){
	auto pi=split(rt,x);
	++tot;
	e[tot].ls=e[tot].rs=0;
	e[tot].sz=1;
	e[tot].zz=x,e[tot].hp=mt()%10000000+1;
	rt=merg(merg(pi.first,tot),pi.second);
}
void delet(int x){
	auto pi=split(rt,x);
	auto ip=split(pi.first,x-1);
	int X=ip.first,Y=ip.second,Z=pi.second;
	pushdown(Y);
	rt=merg(X,merg(merg(e[Y].ls,e[Y].rs),Z));
}
int rk(int x){
	auto pi=split(rt,x-1);
	int ans=e[pi.first].sz;
	rt=merg(pi.first,pi.second);
	return ans;
}
int kr(int x){
	int wz=rt;
	while(1){
		pushdown(wz);
		int he=e[e[wz].ls].sz+1;
		if(x>he)x-=he,wz=e[wz].rs;
		else if(x==he)break;
		else wz=e[wz].ls;
	}
	return e[wz].zz;
}
int l[300005],r[300005];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d%d",&l[i],&r[i]);
	for(int i=1;i<=n;++i){
		int L=l[i],R=r[i];
		int rr=rk(R)+1;
		if(rr<=e[rt].sz){
			delet(kr(rr));
		}
		auto pi=split(rt,L-1);
		auto ip=split(pi.second,R-1);
		++lz[ip.first];++e[ip.first].zz;
		rt=merg(pi.first,merg(ip.first,ip.second));
		inser(L);
	}
	printf("%d\n",e[rt].sz);
	return 0;
}
0