Submission #1308374

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308374		nguyenletrung	Passport (JOI23_passport)	C++20	0 / 100	2131 ms	591992 KiB

passport

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define ins insert
#define pb push_back
#define foru(i,a,b) for(int i=a;i<=b;i++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
//#define int ll
using namespace std;

int n,nq,L[200005],R[200005];
int lef[20][200005],rig[20][200005];
int rmqlef[20][20][200005],rmqrig[20][20][200005];

int tl[800005],tr[800005];

void build(int id,int l,int r)
{
	if(l==r)
	{
		tl[id]=0;
		tr[id]=0;
		return;
	}
	
	int mid=(l+r)/2;
	
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	
	tl[id]=min(tl[id*2],tl[id*2+1]);
	tr[id]=max(tr[id*2],tr[id*2+1]);
}

void updatel(int id,int l,int r,int pos,int w)
{
	if(pos<l||r<pos) return;
	if(l==r)
	{
		tl[id]=w;
		return;
	}
	
	int mid=(l+r)/2;
	
	updatel(id*2,l,mid,pos,w);
	updatel(id*2+1,mid+1,r,pos,w);
	
	tl[id]=min(tl[id*2],tl[id*2+1]);
}

void updater(int id,int l,int r,int pos,int w)
{
	if(pos<l||r<pos) return ;
	if(l==r)
	{
		tr[id]=w;
		return;
	}
	
	int mid=(l+r)/2;
	
	updater(id*2,l,mid,pos,w);
	updater(id*2+1,mid+1,r,pos,w);
	
	tr[id]=max(tr[id*2],tr[id*2+1]);
}

int getl(int id,int l,int r,int u,int v)
{
	if(r<u||v<l) return 1e9;
	if(u<=l&&r<=v)
	{
		return tl[id];
	}
	
	int mid=(l+r)/2;
	
	return min(getl(id*2,l,mid,u,v),getl(id*2+1,mid+1,r,u,v));
}

int getr(int id,int l,int r,int u,int v)
{
	if(r<u||v<l) return -1;
	if(u<=l&&r<=v)
	{
		return tr[id];
	}
	
	int mid=(l+r)/2;
	
	return max(getr(id*2,l,mid,u,v),getr(id*2+1,mid+1,r,u,v));
}

int getlef(int id,int l,int r)
{
	int k=__lg(r-l+1);
	
	return min(rmqlef[k][id][l],rmqlef[k][id][r-(1<<(k))+1]);
}

int getrig(int id,int l,int r)
{
	int k=__lg(r-l+1);
	
	return max(rmqrig[k][id][l],rmqrig[k][id][r-(1<<(k))+1]);
}

bool check(int i,int cnt)
{
	int l=i,r=i;
	for(int i=18;i>=0;i--)
	{
		if((cnt>>(i))&1)
		{
			int newl=l,newr=r;
			newl=getlef(i,l,r);
			newr=getrig(i,l,r);
			l=newl;r=newr;
		}
		
		if(l==1&&r==n) return true;
	}
	
	return false;
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n;
	foru(i,1,n) 
	{
		cin>>L[i]>>R[i];
		lef[0][i]=L[i];
		rig[0][i]=R[i];
	}
	
	for(int k=1;k<=18;k++)
	{
		build(1,1,n);
		for(int i=1;i<=n;i++)
		{
			updatel(1,1,n,i,lef[k-1][i]);
			updater(1,1,n,i,rig[k-1][i]);
		}
		
		for(int i=1;i<=n;i++)
		{
			lef[k][i]=getl(1,1,n,lef[k-1][i],rig[k-1][i]);
			rig[k][i]=getr(1,1,n,lef[k-1][i],rig[k-1][i]);
		}
	}
	
	for(int k=0;k<=18;k++)
	{
		for(int i=0;i<=18;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(k==0)
				{
					rmqlef[k][i][j]=lef[i][j];
					rmqrig[k][i][j]=rig[i][j];
				}
				else
				{
					rmqlef[k][i][j]=min(rmqlef[k-1][i][j],rmqlef[k-1][i][j+(1<<(k-1))]);
					rmqrig[k][i][j]=max(rmqrig[k-1][i][j],rmqrig[k-1][i][j+(1<<(k-1))]);
				}
			}
		}
	}
	
	cin>>nq;
	while(nq--)
	{
		int x;
		cin>>x;
		int l=0,r=n,ans=-1;
		while(l<=r)
		{
			int mid=(l+r)/2;
			
			if(check(x,mid))
			{
				ans=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		
		cout<<ans<<'\n';
	}
	
	
}
/*
em thi cho du co khoc
cung se den ngay phai quen
thien duong van cho ngay em den
*/

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46