Submission #1312940

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312940		vlomaczk	Gift Exchange (JOI24_ho_t4)	C++20	0 / 100	2594 ms	4664 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;

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

	void set(int a, int b, int val) {
		if(a==b) {
			T[a+base] = val;
			return;
		}
		a+=base-1;
		b+=base+1;
		while(a/2 != b/2) {
			if(a%2==0) T[a+1] = max(T[a+1], val);
			if(b%2==1) T[b-1] = max(T[b-1], val);
			a/=2; b/=2;
		}
	}
	
	int query(int x) {
		x += base;
		int ans = -1;
		while(x > 0) {
			ans = max(ans, T[x]);
			x/=2;
		}
		return ans;
	}
};

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] = max(st.query(S[i]), st.query(T[i]));
		st.set(S[i], T[i], i);
	}
	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;
	while(q--) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		bool ans = 1;
		for(int i=l; i<=r; ++i) if(L[i] < l && R[i] > r) ans = 0;
		if(ans) cout << "Yes\n";
		else cout << "No\n";
	}

	return 0;
}

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