Submission #1312947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312947		vlomaczk	Gift Exchange (JOI24_ho_t4)	C++20	10 / 100	151 ms	10924 KiB

Main

#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) return T[a+1];
		if(b%2==1) return 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());
	vector<int> idx(n);
	for(int i=0; i<n; ++i) {
		idx[pary[i].second] = i;
		upd(i, R[pary[i].second]);
	}
	for(int l=0; l<n; ++l) {
		for(auto[r,i] : bucket[l]) {
			int x = lower_bound(pary.begin(), pary.end(), make_pair(l, -1)) - pary.begin();
			if(query(0,x-1) <= r) ans[i] = 1;
			else ans[i] = 0;
		}
		upd(idx[l], 0);
	}
	for(int i=0; i<q; ++i) {
		if(ans[i]) cout << "Yes\n";
		else cout << "No\n";
	}

	return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 10 / 10
• Subtask 4: 0 / 31
• Subtask 5: 0 / 8
• Subtask 6: 0 / 12
• Subtask 7: 0 / 18
• Subtask 8: 0 / 12