제출 #1343583

#제출 시각아이디문제언어결과실행 시간메모리
1343583joacruGift Exchange (JOI24_ho_t4)C++20
100 / 100
1690 ms222712 KiB
#include <bits/stdc++.h>

#define forn(i,n) for(int i=0;i<int(n);++i)
#define fort(i,n) for(int i=0;i<=int(n);++i)
#define fori(i,a,n) for(int i=a;i<int(n);++i)
#define forit(i,a,n) for(int i=a;i<=int(n);++i)
#define ALL(v) v.begin(),v.end()
#define SZ(v) (int)v.size()

#define DBG(a) cerr<<#a<<" = "<<(a)<<endl
#define DBGA(a) cerr<<#a<<" = "<<(a)<<", ";
#define DBG2(a,b) do{DBGA(a)DBG(b);}while(0)
#define DBG3(a,b,c) do{DBGA(a)DBGA(b)DBG(c);}while(0)
#define DBG4(a,b,c,d) do{DBGA(a)DBGA(b)DBGA(c)DBG(d);}while(0)

#define LINE cerr<<"===================================="<<endl

using namespace std;

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v){
	os<<"[";
	forn(i,v.size()){
		if(i) os<<" ";
		os<<v[i];
	}
	os<<"]";
	return os;
}

typedef long long ll;
typedef long double ld;

struct ST{
	int n;
	vector<int> st,lz;
	ST(int m){
		n=1<<(32-__builtin_clz(m-1));
		st.resize(2*n-1,-1);
		lz.resize(2*n-1,-1);
	}
	void push(int i){
		if(lz[i]==-1) return;
		if(i<n-1){
			lz[2*i+1] = lz[i];
			lz[2*i+2] = lz[i];
		}
		st[i] = lz[i];
		lz[i] = -1;
	}
	void update(int ul, int ur, int v, int l, int r, int i){
		push(i);
		if(l>=ur||r<=ul) return;
		if(l>=ul&&r<=ur){
			lz[i] = v;
			push(i);
			return;
		}
		int m=(l+r)/2;
		update(ul,ur,v,l,m,2*i+1);
		update(ul,ur,v,m,r,2*i+2);
		st[i] = max(st[2*i+1],st[2*i+2]);
	}
	void update(int l, int r, int v){
		update(l,r,v,0,n,0);
	}
	int query(int ql, int qr, int l, int r, int i){
		push(i);
		if(l>=qr||r<=ql) return -1;
		if(l>=ql&&r<=qr) return st[i];
		int m=(l+r)/2;
		return max(query(ql,qr,l,m,2*i+1),query(ql,qr,m,r,2*i+2));
	}
	int query(int l, int r){
		return query(l,r,0,n,0);
	}
};

struct MST{
	int n;
	vector<vector<pair<int,int>>> vs; // valoress
	vector<vector<int>> ss; // sufijo hacia la derecha
	MST(vector<int> l, vector<int> r){
		int m=SZ(l);
		n=1<<(32-__builtin_clz(m-1));
		vs.resize(2*n-1);
		ss.resize(2*n-1);
		for(int i=n-1,j=0;j<m;++i,++j) vs[i].push_back({l[j],r[j]});
		build(0);
	}
	void build(int i){
		if(i<n-1){ // se puede mejorar
			build(2*i+1);
			build(2*i+2);
			vs[i].resize(SZ(vs[2*i+1])+SZ(vs[2*i+2]));
			merge(ALL(vs[2*i+1]),ALL(vs[2*i+2]),vs[i].begin());
			//~ vs[i].insert(vs[i].end(),ALL(vs[2*i+1]));
			//~ vs[i].insert(vs[i].end(),ALL(vs[2*i+2]));
			//~ sort(ALL(vs[i]));
		}
		ss[i].resize(SZ(vs[i]));
		if(!SZ(ss[i])) return;
		ss[i][0] = vs[i][0].second;
		for(int j=1;j<SZ(ss[i]);++j){
			ss[i][j] = max(ss[i][j-1],vs[i][j].second);
		}
	}
	bool query(int ql, int qr, int l, int r, int i){
		if(l>=qr||r<=ql) return 1;
		if(l>=ql&&r<=qr){
			int j=int(lower_bound(ALL(vs[i]),make_pair(ql,-1))-vs[i].begin());
			//~ DBG3(j,SZ(vs[i]),SZ(ss[i]));
			if(j == 0) return 1;
			return ss[i][j-1] < qr;
		}
		int m=(l+r)/2;
		return query(ql,qr,l,m,2*i+1)&&query(ql,qr,m,r,2*i+2);
	}
	bool query(int l, int r){
		return query(l,r,0,n,0);
	}
};

void solve(){
	
	int n;
	cin>>n;
	
	vector<int> a(n), b(n);
	
	for(int &x: a){
		cin>>x;
		--x;
	}
	for(int &x: b){
		cin>>x;
		--x;
	}
	
	vector<int> L(n), R(n);
	forn(_,2){
		ST some(2*n);
		forn(i,n){
			L[i] = some.query(b[i],a[i]+1);
			some.update(b[i],a[i]+1,i);
		}
		reverse(ALL(a));
		reverse(ALL(b));
		swap(L,R);
	}
	
	reverse(ALL(R));
	for(int &x: R) x = n-x-1;
	
	//~ DBG2(L,R);
	
	MST gift(L,R);
	
	int q;
	cin>>q;
	
	while(q--){
		int l, r;
		cin>>l>>r;
		l--;
		//~ DBG2(l,r);
		if(gift.query(l,r)) cout<<"Yes\n";
		else cout<<"No\n";
	}
}

int main() {
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	#ifdef LOCAL
		assert(freopen("D.in", "r", stdin));
		//~ freopen("output.out", "w", stdout);
	#endif
	
	#ifdef LOCAL
	int tcs; cin>>tcs;
	while(tcs--)
	#endif
	solve();

	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...