Submission #1346179

#TimeUsernameProblemLanguageResultExecution timeMemory
1346179akqxolotlGift Exchange (JOI24_ho_t4)C++20
0 / 100
0 ms344 KiB
//Segment Tree is a State of Mind
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr<<#x<<" is "<<x<<endl;
#define debugp(x,y) cerr<<#x<<' '<<#y<<" is "<<x<<' '<<y<<endl;
#define debugl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p<<" ";cerr<<endl;
#define debugpl(x) cerr<<#x<<" is ";for(auto p:x)cerr<<p.first<<" "<<p.second<<" , ";cerr<<endl;

#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
#define pb push_back
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define rdint(x,y) rnd()%(y-x+1)+x

const int inf=4e18+5;
const int mod=1e9+7;
const int mod2=998244353;
const int mod3=1e9+9;
const int maxn=2e5+5;

struct qr{
	string m;
	int x,t;
};

struct node{
	
	int s,e,m;
	int v=0;
	int z=0;
	node *l=nullptr,*r=nullptr;
	
	node(int S,int E){
		s=S,e=E,m=(s+e)/2;
	}
	
	void cre(){
		if(s==e)return;
		l=new node(s,m);
		r=new node(m+1,e);
	}
	
	void prop(){
		v+=z;
		if(s!=e){
			if(l==nullptr)cre();
			l->z+=z;
			r->z+=z;
		}
		z=0;
	}
	
	void ud(int S,int E,int V){
		prop();
		if(S==s&&E==e){
			z+=V;
			prop();
			return;
		}
		if(l==nullptr)cre();
		if(E<=m)l->ud(S,E,V);
		else if(S>m)r->ud(S,E,V);
		else l->ud(S,m,V),r->ud(m+1,E,V);
		l->prop(),r->prop();
		v=max(l->v,r->v);
	}
	
};		

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	int a[n],b[n];
	for(int i=0;i<n;i++)cin>>a[i];
	for(int i=0;i<n;i++)cin>>b[i];
	set<int> fs,fe,f;
	
	for(int i=0;i<n-1;i++){
		if(a[i]<b[i+1])fs.insert(i),fe.insert(i+1);
	}
	if(b[1]>a[0])f.insert(0);
	if(b[n-1]>a[n-2])f.insert(n-1);
	for(int i=1;i<n-1;i++){
		if(b[i]>a[i-1]&&b[i+1]>a[i])f.insert(i);
	}
	debugl(fs)debugl(fe)debugl(f)
	int q;cin>>q;
	while(q--){
		int l,r;cin>>l>>r;
		l--,r--;
		/*vi v;
		for(int i=l-1;i<r;i++)v.pb(b[i]);//start
		sort(v.begin(),v.end());
		vi u;
		for(int i=l-1;i<r;i++)u.pb(a[i]);//end
		sort(u.begin(),u.end());
		bool f=1;
		for(int i=0;i<sz(v);i++){
			int eb=lower_bound(u.begin(),u.end(),v[i])-u.begin();
			int sa=sz(v)-(upper_bound(v.begin(),v.end(),u[i])-v.begin());
			if(eb+sa==sz(v)-1)f=0;
		}
		if(f)cout<<"Yes\n";
		else cout<<"No\n";*/
		if(fs.find(l)!=fs.end()||fe.find(r)!=fe.end()||*f.lower_bound(l)<=r)cout<<"No\n";
		else cout<<"Yes\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...