제출 #1328229

#제출 시각아이디문제언어결과실행 시간메모리
1328229jellybeanGift Exchange (JOI24_ho_t4)C++20
100 / 100
2007 ms241616 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
typedef pair<int,int> pii;

const int N = 500005;
vector<pii>query[N];
int ans[N];
int a[N], b[N];
vector<int>r[N];

struct node{ //range set range max
	int s,e,m,val=0,lazy=-1;
	node *l = nullptr, *r = nullptr;
	
	node(int S, int E){
		s=S, e=E, m=(s+e)/2;
		if(s!=e){
			l = new node(s,m);
			r = new node(m+1,e);
		}
	}
	
	void prop(){
		if(lazy == -1) return;
		val = lazy;
		if(s != e){
			l->lazy = lazy;
			r->lazy = lazy;
		}
		lazy = -1;
	}
	
	void up(int S, int E, int v){
		prop();
		if(s==S and e==E) lazy = v;
		else{
			if(E<=m) l->up(S,E,v);
			else if(S>m) r->up(S,E,v);
			else l->up(S,m,v), r->up(m+1,E,v);
			l->prop(), r->prop();
			val = max(l->val,r->val);
		}
	}
	
	int qr(int S, int E){
		prop();
		if(s==S and e==E) return val;
		else if(E<=m) return l->qr(S,E);
		else if(S>m) return r->qr(S,E);
		else return max(l->qr(S,m), r->qr(m+1,E));
	}
}*root;

struct node1{
	int s,e,m,val=0;
	node1 *l = nullptr, *r = nullptr;
	
	node1(int S, int E){
		s=S, e=E, m=(s+e)/2;
		if(s!=e){
			l = new node1(s,m);
			r = new node1(m+1,e);
		}
	}
	
	void up(int x, int v){
		if(s==e) val = v;
		else{
			if(x<=m) l->up(x,v);
			else r->up(x,v);
			val = min(l->val,r->val);
		}
	}
	
	int qr(int S, int E){
		if(s==S and e==E) return val;
		else if(E<=m) return l->qr(S,E);
		else if(S>m) return r->qr(S,E);
		else return min(l->qr(S,m), r->qr(m+1,E));
	}
}*root1;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=1; i<=n; i++) cin>>a[i];
	for(int i=1; i<=n; i++) cin>>b[i];
	
	int q; cin>>q;
	for(int i=0; i<q; i++){
		int L,R; cin>>L>>R;
		query[R].pb({L,i});
	}
	
	root = new node(1,2*n);
	root1 = new node1(1,n);
	
	for(int i=1; i<=n; i++){
		int x = root->qr(b[i],a[i]);
		root1->up(i,x);
		root->up(b[i],a[i],i);
	}
	
	root->up(1,2*n,-(n+1));
	for(int i=n; i>=1; i--){
		int x = root->qr(b[i],a[i]);
		r[-x].pb(i);
		root->up(b[i],a[i],-i);
	}
	
	for(int i=1; i<=n; i++){
		for(auto j: r[i]) root1->up(j,n+1);
		for(auto [l,j]: query[i]){
			int x = root1->qr(l,i);
			if(x<l) ans[j] = 1;
		}
	}
	
	for(int i=0; i<q; i++){
		if(ans[i]) cout<<"No\n";
		else cout<<"Yes\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...