Submission #1342561

#TimeUsernameProblemLanguageResultExecution timeMemory
1342561PieArmyPassport (JOI23_passport)C++20
6 / 100
218 ms18440 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

struct Seg{
	int n;
	vector<pair<int,int>>tree;
	void init(int N){
		n=N;
		tree.resize(n<<2,{-1e9,0});
	}
	int l,r;
	void up(int node=1,int left=1,int right=-1){
		if(right==-1)right=n;
		if(left==right){
			tree[node]={r,left};
			return;
		}
		if(l>mid)up(node*2+1,mid+1,right);
		else up(node*2,left,mid);
		tree[node]=max(tree[node*2],tree[node*2+1]);
	}
	void update(int tar,int x){
		l=tar;r=x;
		up();
	}
	pair<int,int> qu(int node=1,int left=1,int right=-1){
		if(right==-1)right=n;
		if(left>=l&&right<=r)return tree[node];
		if(left>r||right<l)return {-1e9,0};
		return max(qu(node*2,left,mid),qu(node*2+1,mid+1,right));
	}
	int query(int left,int right){
		l=left;r=right;
		return qu().sc;
	}
};

int n;
pair<int,int>ara[200023];
int suf[200023],ans[200023],opt[200023];
int perl[200023],perr[200023];
Seg rig,seg;

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n;
	seg.init(n);
	rig.init(n);
	for(int i=1;i<=n;i++){
		cin>>ara[i].fr>>ara[i].sc;
		perl[i]=i;
		perr[i]=i;
		opt[i]=ans[i]=1e9;
		rig.update(i,ara[i].sc);
	}
	sort(perl+1,perl+n+1,[&](const int &x,const int &y){
		return ara[x].fr<ara[y].fr;
	});
	sort(perr+1,perr+n+1,[&](const int &x,const int &y){
		return ara[x].sc>ara[y].sc;
	});
	suf[n+1]=n;
	for(int i=n;i>=2;i--){
		suf[i]=min(suf[i+1],ara[i].fr);
	}
	for(int i=2;i<=n;i++){
		if(suf[i]>=i){
			suf[i]=1e9;
		}
		else suf[i]=suf[suf[i]]+1;
	}
	for(int i=1;i<=n;i++){
		if(ara[perr[i]].sc==n){
			opt[perr[i]]=1;
			continue;
		}
		int x=rig.query(ara[perr[i]].fr,ara[perr[i]].sc);
		if(x){
			opt[perr[i]]=opt[x]+1;
		}
	}
	for(int i=1;i<=n;i++){
		int x=seg.query(ara[perl[i]].fr,ara[perl[i]].sc);
		if(x){
			ans[perl[i]]=ans[x]+1;
		}
		//cerr<<ans[perl[i]]<<":";
		if(ara[perl[i]].fr==1)suf[perl[i]]=0;
		ans[perl[i]]=min(ans[perl[i]],opt[perl[i]]+suf[perl[i]]);
		//cerr<<ans[perl[i]]<<"*"<<perl[i]<<endl;
		seg.update(perl[i],-ans[perl[i]]);
	}
	for(int i=1;i<=n;i++){
		if(ans[i]>n)ans[i]=-1;
	}
	int q;cin>>q;
	while(q--){
		int x;cin>>x;
		cout<<ans[x]<<endl;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...