제출 #1312946

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312946		vlomaczk	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	2595 ms	6880 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 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: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 31 / 31
• Subtask 5: 0 / 8
• Subtask 6: 0 / 12
• Subtask 7: 0 / 18
• Subtask 8: 0 / 12