제출 #1343486

#제출 시각아이디문제언어결과실행 시간메모리
1343486JuanJLGift Exchange (JOI24_ho_t4)C++20
50 / 100
2594 ms14360 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 long long ll;

/*
para un rango como veo cual es el primer rango que intersecta conmigo
*/

#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));
	}
	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); }
};

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(){
	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)); 

	forn(i,0,n) stmax.upd(i,a[i]);
	forn(i,0,n){
		while(bord.back().fst>aord[i].fst){
			stmax.upd(bord.back().snd,-1);
			bord.pop_back();
		}
		
		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);
	}

	bord.clear();
	aord.clear();

	forn(i,0,n) bord.pb({b[i],i}); sort(ALL(bord));
	forn(i,0,n) aord.pb({a[i],i}); sort(ALL(aord)); reverse(ALL(aord));
	forn(i,0,n) stmin.upd(i,b[i]);
	forn(i,0,n){
		while(aord.back().fst<bord[i].fst){
			stmin.upd(aord.back().snd,INF);
			aord.pop_back();
		}

		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);
	}

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

	ll q; cin>>q;
	forn(i,0,q){
		ll l,r; cin>>l>>r; l--; r--;
		bool yes=true;
		forn(j,l,r+1){
			if(lle[j]<l&& rri[j]>r)yes=false; 
		}
		if(yes) cout<<"Yes\n";
		else cout<<"No\n";
	}
	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...