Submission #1343550

#TimeUsernameProblemLanguageResultExecution timeMemory
1343550JuanJLGift Exchange (JOI24_ho_t4)C++20
88 / 100
2595 ms33512 KiB
#include <bits/stdc++.h>

#define fst first
#define snd second
#define pb push_back
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(),x.end()
#define forn(i,a,b) for(int i = a; i<b; i++)
#define mset(a,v) memset(a,v,sizeof(a))
#define FIN ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;
typedef int ll;

#define INF ((ll)1000000000)

struct STreeMin{
	ll n;
	vector<ll> st;

	STreeMin(ll n):n(n),st(4*n+5,INF) {}
	void upd(ll k, ll l, ll r, ll p, ll v){
		if(l+1==r){ st[k]=v; return; }
		ll mid = (l+r)/2;
		if(mid>p) upd(2*k,l,mid,p,v);
		else upd(2*k+1,mid,r,p,v);
		st[k]=min(st[2*k],st[2*k+1]);
	}
	ll query(ll k, ll l, ll r, ll L, ll R){
		if(l>=R||r<=L) return INF;
		if(l>=L && r<=R) return st[k];
		ll mid = (l+r)/2;
		return min(query(2*k,l,mid,L,R),query(2*k+1,mid,r,L,R));
	}
	pair<ll,ll> bquery(ll k, ll l, ll r, ll L, ll R, ll V){
		if(l>=R||r<=L) return {-1,INF};
		ll mid = (l+r)/2;
		
		if(l+1==r&&st[k]<V) return {l,st[k]};
		if(l+1==r) return {-1,st[k]};
		if(l>=L&&r<=R){
			if(st[k]<V){
				if(st[2*k+1]<V){
					return bquery(2*k+1,mid,r,L,R,V);
				}else{
					return bquery(2*k,l,mid,L,R,V);
				}
			}else{
				return {-1,st[k]};
			}
		}

		pair<ll,ll> left = bquery(2*k,l,mid,L,R,V);
		pair<ll,ll> right = bquery(2*k+1,mid,r,L,R,V);
		if(right.snd<V) return right;
		return left;
	}
	void upd(ll p, ll v){ upd(1,0,n,p,v); }
	ll query(ll l, ll r){ return query(1,0,n,l,r); }
	ll bquery(ll l, ll r, ll v){ return bquery(1,0,n,l,r,v).fst; }
};

struct STreeMax{
	ll n;
	vector<ll> st;

	STreeMax(ll n):n(n),st(4*n+5,-1) {}
	void upd(ll k, ll l, ll r, ll p, ll v){
		if(l+1==r){ st[k]=v; return; }
		ll mid = (l+r)/2;
		if(mid>p) upd(2*k,l,mid,p,v);
		else upd(2*k+1,mid,r,p,v);
		st[k]=max(st[2*k],st[2*k+1]);
	}
	ll query(ll k, ll l, ll r, ll L, ll R){
		if(l>=R||r<=L) return -1;
		if(l>=L && r<=R) return st[k];
		ll mid = (l+r)/2;
		return max(query(2*k,l,mid,L,R),query(2*k+1,mid,r,L,R));
	}
	void upd(ll p, ll v){ upd(1,0,n,p,v); }
	ll query(ll l, ll r){ return query(1,0,n,l,r); }
};

int main(){ FIN;
	ll n; cin>>n;
	vector<ll> a(n); forn(i,0,n) cin>>a[i];
	vector<ll> b(n); forn(i,0,n) cin>>b[i];

	STreeMax stmax(n+5);
	STreeMin stmin(n+5);

	vector<ll> lle(n,-1);
	vector<ll> rri(n,n+1);

	vector<pair<ll,ll>> aord; forn(i,0,n) aord.pb({a[i],i});
	sort(ALL(aord)); reverse(ALL(aord));

	vector<pair<ll,ll>> bord; forn(i,0,n) bord.pb({b[i],i});
	sort(ALL(bord)); 

	ll J = SZ(bord)-1;

	forn(i,0,n) stmax.upd(i,a[i]);
	forn(i,0,n){
		while(J>=0 && bord[J].fst>aord[i].fst){
			stmax.upd(bord[J].snd,-1);
			J--;
		}
		
		ll I = aord[i].snd;
		//cout<<I<<"::::\n";
		ll l = I+1; ll r = n+5;
	
		while(l<=r){
			ll mid = (l+r)/2;
			//cout<<l<<" "<<r<<" "<<"["<<I+1<<" "<<mid+1<<") "<<stmax.query(I+1,mid+1)<<"\n";
			if(stmax.query(I+1,mid+1)>b[I]){
				r=mid-1;
			}else{
				l=mid+1;
			}
		}

		rri[I]=min(rri[I],l);
	}

	forn(i,0,n) stmin.upd(i,b[i]);
	J=SZ(aord)-1;
	forn(i,0,n){
		while(J>=0 && aord[J].fst<bord[i].fst){
			stmin.upd(aord[J].snd,INF);
			J--;
		}

		ll I = bord[i].snd;
		ll l = 0; ll r=I-1;
		while(l<=r){
			ll mid = (l+r)/2;

			if(stmin.query(mid,I)<a[I]){
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		//lle[I]=max(lle[I],r);
		lle[I]=max(lle[I],(0<I?stmin.bquery(0,I,a[I]):-1));
	}

	//forn(i,0,n) cout<<lle[i]<<" lr "<<rri[i]<<'\n';

	STreeMax stmaxres(n+5);
	
	vector<pair<pair<ll,ll>,ll>> que;
	ll q; cin>>q;
	forn(i,0,q){
		ll l,r; cin>>l>>r; l--; r--;
		que.pb({{l,r},i});
	}
	sort(ALL(que));

	vector<pair<ll,ll>> liord; forn(i,0,n) liord.pb({lle[i],i});
	sort(ALL(liord)); reverse(ALL(liord));

	vector<string> res(q);
	forn(i,0,q){
		while(!liord.empty() && liord.back().fst<que[i].fst.fst){
			stmaxres.upd(liord.back().snd,rri[liord.back().snd]); 
			liord.pop_back();
		}
		
		bool yes=true;
		//cout<<que[i].snd<<" "<<stmaxres.query(que[i].fst.fst,que[i].fst.snd+1)<<'\n';
		if(stmaxres.query(que[i].fst.fst,que[i].fst.snd+1)>que[i].fst.snd) yes=false;
		if(yes) res[que[i].snd]="Yes\n";
		else res[que[i].snd]="No\n";
	}
	for(auto i:res) cout<<i;
	return 0;
}
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...