Submission #1316470

#TimeUsernameProblemLanguageResultExecution timeMemory
1316470WH8Gift Exchange (JOI24_ho_t4)C++17
100 / 100
2086 ms205892 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define mt make_tuple
#define mp make_pair
#define pb push_back
#define int long long 
#define f first
#define s second
#define pll pair<long long, long long>
#define iii tuple<int,int,int>

void chmin(int & x, int v){ x=min(x, v);}
void chmax(int & x, int v){ x=max(x, v);}

struct node {
	int s, e, m, v, lz;
	node *l, *r;
	node (int S, int E){
		s=S, e=E, m=(s+e)/2, v=0, lz=-1e9;
		if(s!=e){
			l=new node(s, m);
			r=new node(m+1, e);
		}
	}
	void prop(){
		if(s==e or lz==-1e9)return;
		l->v=lz, r->v=lz, l->lz=lz, r->lz=lz;
		lz=-1e9;
	}
	int combine(int a, int b){
		return max(a, b);
	}
	void upd(int S, int E, int V){ // range set;
		if((S==s and E==e) or s==e){
			v=V;
			lz=V;
			return;
		}
		prop();
		if (E<=m) l->upd(S,E,V);
		else if (S>m) r->upd(S,E,V);
		else l->upd(S,m,V),r->upd(m+1,E,V);
		v=combine(l->v,r->v);
	}
	int qry(int S,int E){
		if((S==s and E==e) or s==e){
			return v;
		}
		prop();
		if(E<=m)return l->qry(S,E);
		if(S>m)return r->qry(S,E);
		return combine(l->qry(S,m),r->qry(m+1,E));
	}
}*root;

const int maxn=500005, maxq=200005;
vector<iii> qs;
vector<int> ans(maxq, 1), l(maxn, 0), r(maxn, 500005);
void dnc(int s, int e, vector<iii> cq){
	int n=e-s+1, m=(n+1)/2;
	/*printf("dnc %lld %lld, n %lld, m %lld\n", s,e,n,m);
	for(auto [a, b, c] : cq)printf("(%lld,%lld,%lld) ",a,b,c);
	cout<<endl;*/
	// 0 1 ... n n+1;
	vector<vector<pll>> todo(n+2);
	vector<iii> lqs, rqs;
	for(auto [ql, qr, qi] : cq){
		if(qr <= (s+e)/2) lqs.pb({ql,qr,qi});
		else if(ql > (s+e)/2) rqs.pb({ql, qr, qi});
		else {
			todo[ql-s+1].pb({qr, qi});
			todo[qr-s+1].pb({ql, qi});
		}
	}
	/*vector<int> mn(n+2, 1e9), mx(n+2, -1);
	for(int i=1;i<=m;i++){
		chmax(mx[max(l[s+i-1]-s+1,0ll)], r[s+i-1]-s+1);
	}
	for(int i=m+1;i<=n;i++){
		chmin(mn[min(r[s+i-1]-s+1,n+1)], l[s+i-1]-s+1);
	}
	int rmx=-1, rmn=1e9;
	for(int i=0;i<=m;i++){
		for(auto [qr, qi] : todo[i]){
			if(rmx > qr) ans[qi]=0;
		}
		printf("i %lld, chmaxing with %lld\n", i, mx[i]);
		rmx=max(rmx, mx[i]);
	}
	for(int i=n+1;i>m;i--){
		for(auto [ql, qi] : todo[i]){
			if(rmn < ql) ans[qi]=0;
		}
		printf("i %lld, chmin with %lld\n", i, mn[i]);
		rmn=min(rmn, mn[i]);
	}*/
	priority_queue<pll> pq1;
	priority_queue<pll,vector<pll>, greater<pll>> pq2;
	for(int i=m;i>0;i--){
		pq1.push(mp(r[s+i-1], l[s+i-1]));
		//printf("pushed in r[s+i-1] %lld, l[s+i-1] %lld\n", r[s+i-1], l[s+i-1]);
		while(!pq1.empty() and pq1.top().s >= s+i-1) pq1.pop();
		/*auto it=s.upper_bound(mp(l[i], (int)1e15));
		while(it != s.end() and (*it).s <= r[i])it=s.erase(it);
		if(it != s.begin() and (*prev(it)).s >= r[i]);
		else it.insert(mp(l[i], r[i]));*/
		for(auto [qr, qi] : todo[i]){
			//printf("answering %lld %lld, top %lld\n", qr, qi, (pq1.empty()? -1 : pq1.top().f));
			if(!pq1.empty() and pq1.top().f > qr) ans[qi]=0;
		}
	}
	for(int i=m+1;i<=n;i++){
		pq2.push(mp(l[s+i-1], r[s+i-1]));
		while(!pq2.empty() and pq2.top().s <= s+i-1) pq2.pop();
		for(auto [ql, qi] : todo[i]){
			//printf("answering %lld %lld, top %lld\n", ql, qi, (pq2.empty()? -1 : pq2.top().f));
			if(!pq2.empty() and pq2.top().f < ql) ans[qi]=0;
		}
	}
	if(!lqs.empty())dnc(s, (s+e)/2, lqs);
	if(!rqs.empty())dnc((s+e)/2+1, e, rqs);
}

signed main(){
	int n;cin>>n;
	vector<int> a(n+2, 0), b(n+2, 0);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	root=new node(1, 2*n);
	for(int i=1;i<=n;i++){
		l[i]=root->qry(b[i], a[i]);
		root->upd(b[i], a[i], i);
	}
	root->upd(1, 2*n, -n-1);
	for(int i=n;i>=1;i--){
		r[i]=-root->qry(b[i], a[i]);
		root->upd(b[i], a[i], -i);
	}
	/*for(int i=1;i<=n;i++){
		printf("i %lld l[i] %lld r[i] %lld\n", i, l[i], r[i]);
	}*/
	//return 0;
	int q;cin>>q;
	for(int i=0;i<q;i++){
		int a,b;cin>>a>>b;
		qs.pb({a, b, i});
	}
	dnc(1, n, qs);
	for(int i=0;i<q;i++){
		if(ans[i])cout<<"Yes\n";
		else cout<<"No\n";
	}
}
#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...