Submission #1312960

#TimeUsernameProblemLanguageResultExecution timeMemory
1312960vlomaczkGift Exchange (JOI24_ho_t4)C++20
100 / 100
880 ms39440 KiB
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct SegTree {
	int base;
	vector<int> T, L;

	SegTree(int n) {
		base = 1;
		while(base < n) base *= 2;
		T.assign(2*base,-1);
		L.assign(2*base,-1);
	}

	void push(int v, int l, int r) {
		if(L[v]==-1 || v >= base) return;
		T[l] = T[r] = L[l] = L[r] = L[v];
		L[v] = -1;
	}

	void set(int v, int a, int b, int p, int k, int val) {
		if(b < p || k < a) return;
		if(p <= a && b <= k) {
			T[v] = L[v] = val;
			return;
		}
		int l = 2*v; int r = 2*v+1; int m=(a+b)/2;
		push(v,l,r);
		set(l,a,m,p,k,val);
		set(r,m+1,b,p,k,val);
		T[v] = max(T[l], T[r]);
	}
	
	int query(int v, int a, int b, int p, int k) {
		if(b < p || k < a) return -1;
		if(p <= a && b <= k) return T[v];
		int l = 2*v; int r = 2*v+1; int m=(a+b)/2;
		push(v,l,r);
		return max(query(l,a,m,p,k), query(r,m+1,b,p,k));
	}
};

vector<int> compute(vector<int> S, vector<int> T) {
	int n = S.size();
	SegTree st(2*n+5);
	vector<int> res(n);
	for(int i=0; i<n; ++i) {
		res[i] = st.query(1,0,st.base-1, S[i], T[i]);
		st.set(1,0,st.base-1, S[i], T[i], i);
	}
	return res;
}

int base = 1<<19;
vector<int> T(2*base,0);

void upd(int x, int val) {
	x += base;
	T[x] = val;
	x/=2;
	while(x > 0) {
		T[x] = max(T[x+x], T[x+x+1]);
		x/=2;
	}
}

int query(int a, int b) {
	if(a==b) return T[a+base];
	a += base-1;
	b += base+1;
	int res = 0;
	while(a/2 != b/2) {
		if(a%2==0) res = max(res, T[a+1]);
		if(b%2==1) res = max(res, T[b-1]);
		a/=2; b/=2;
	}
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;
	vector<int> S(n), T(n);
	for(int i=0; i<n; ++i) cin >> T[i];
	for(int i=0; i<n; ++i) cin >> S[i];
	vector<int> L = compute(S, T);
	reverse(S.begin(), S.end()); reverse(T.begin(), T.end());
	vector<int> R = compute(S, T);
	reverse(S.begin(), S.end()); reverse(T.begin(), T.end());
	reverse(R.begin(), R.end());
	for(auto &i : R) i = n-i-1;
	int q; cin >> q;
	vector<int> ans(q);
	vector<vector<pair<int, int>>> bucket(n);
	for(int t=0; t<q; ++t) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		bucket[l].push_back({r,t});
	}
	vector<pair<int, int>> pary;
	for(int i=0; i<n; ++i) pary.push_back({L[i], i});
	sort(pary.begin(), pary.end());
	int curr = 0;
	for(int l=0; l<n; ++l) {
		while(curr < pary.size() && pary[curr].first < l) {
			upd(pary[curr].second, R[pary[curr].second]);
			curr++;
		}
		for(auto[r,i] : bucket[l]) {
			if(query(l, r) <= r) ans[i] = 1;
			else ans[i] = 0;
		}
	}
	for(int i=0; i<q; ++i) {
		if(ans[i]) 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...