結果

問題 No.686 Uncertain LIS
コンテスト
ユーザー xxyPerta
提出日時 2023-12-31 18:06:23
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,752 bytes
コンパイル時間 1,661 ms
コンパイル使用メモリ 169,264 KB
実行使用メモリ 14,844 KB
最終ジャッジ日時 2024-09-27 17:08:00
合計ジャッジ時間 8,233 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 WA * 8 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
const int N=6e5+10;
int n,ans,cnt,root;
int Fa[N],num[N],son[N][2],tag[N];
inline void Max(int &x,int y) {x=x>y?x:y;}
bool loc(int x) {return son[Fa[x]][1]==x;}
void inc(int x)
{
	if(!tag[x]||!x) return;
    num[son[x][0]]+=tag[x];
	tag[son[x][0]]+=tag[x];
    num[son[x][1]]+=tag[x];
	tag[son[x][1]]+=tag[x];
	tag[x]=0;
}
void rot(int x)
{
	int fa=Fa[x],ffa=Fa[fa],L=loc(x);
	inc(x),inc(fa);
    son[fa][L]=son[x][L^1];
    Fa[son[fa][L]]=fa;
	if(ffa) son[ffa][loc(fa)]=x;
	Fa[fa]=x;
	Fa[x]=ffa;
    son[x][L^1]=fa;
}
void splay(int x,int up)
{
	for(int fa;(fa=Fa[x])!=up;rot(x))
        if(Fa[fa]!=up) rot(loc(x)==loc(fa)?fa:x);
	if(!up) root=x;
}
int pree(int x)
{
    int now=root,res=-1;
    while(now)
    {
        inc(now);
        if(num[now]<x) res=now,now=son[now][1];
        else now=son[now][0];
    }
    return res;
}
int suff(int x)
{
	int now=root,res=-1;
	while(now)
	{
		inc(now);
        if(num[now]>=x) res=now,now=son[now][0];
		else now=son[now][1];
	}
    return res;
}
void add(int x)
{
    int ned=suff(x);
    if(!~ned)
    {
        ned=pree(x);
        assert(~ned);
        splay(ned,0);
        inc(ned);
        Fa[++cnt]=ned,num[cnt]=x,son[cnt][1]=son[ned][1];
        Fa[son[ned][1]]=cnt;
        son[ned][1]=cnt;
        splay(cnt,0);
        return;
    }
    splay(ned,0);
    inc(ned);
    Fa[++cnt]=ned,num[cnt]=x,son[cnt][0]=son[ned][0];
    Fa[son[ned][0]]=cnt;
    son[ned][0]=cnt;
    splay(cnt,0);
}
void del(int x)
{
    while(1)
        if(son[x][0]) rot(son[x][0]);
        else if(son[x][1]) rot(son[x][1]);
        else break;
    son[Fa[x]][loc(x)]=0;
    splay(Fa[x],0);
}
void dfs(int x)
{
    ++ans;
    if(son[x][0]) dfs(son[x][0]);
    if(son[x][1]) dfs(son[x][1]);
}
int main()
{
    n=read();
    cnt=root=1;
    for(int i=1,l,r;i<=n;i++)
    {
        l=read(),r=read();
        if(i==1) {num[1]=l;continue;}
        int suf=suff(r),ned=pree(l);
        if(~suf&&~ned)
        {
            splay(suf,0);
            splay(ned,suf);
            num[son[ned][1]]++;
            tag[son[ned][1]]++;
        }
        else if(~suf)
        {
            splay(suf,0);
            num[son[suf][1]]++;
            tag[son[suf][1]]++;
        }
        else if(~ned)
        {
            splay(ned,0);
            num[son[ned][1]]++;
            tag[son[ned][1]]++;
        }
        else
        {
            num[root]++;
            tag[root]++;
        }
        add(l);
        if(~suf) del(suf);
        num[0]=tag[0]=0;
    }
    dfs(root);
    printf("%d\n",ans);
    return 0;
}
0