제출 #1270559

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270559		vlomaczk	Gift Exchange (JOI24_ho_t4)	C++20	50 / 100	2592 ms	8184 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>;

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

	int N;
	cin >> N;
	vector<int> x(N), y(N);
	for(int i=0; i<N; ++i) cin >> x[i];
	for(int i=0; i<N; ++i) cin >> y[i];
	int q;
	cin >> q;
	while(q--) {
		int l, r; cin >> l >> r;
		vector<int> a,b; --l; --r;
		vector<int> t(2*N+1);
		priority_queue<int> left;
		set<int> after; set<int> before;
		for(int i=l; i<=r; ++i) {
			a.push_back(x[i]);
			b.push_back(y[i]);
			t[y[i]] = x[i];
			t[x[i]] = y[i];
		}
		int n = a.size();
		sort(b.begin(), b.end());
		reverse(b.begin(), b.end());
		vector<int> idx(2*N+1);
		for(int i=0; i<n; ++i) {
			idx[b[i]] = idx[t[b[i]]] = i;
			left.push(a[i]);
		}
		bool good = 1;
		vector<int> done(n+1);
		for(int s=0; s<n; ++s) {
			while(left.size() && left.top() > b[s]) {
				int v = left.top();
				if(t[v] <= b[s]) after.insert(idx[v]);
				else before.insert(idx[v]);
				left.pop();
			}
			after.erase(s);
			if(after.size()) {
				done[*after.begin()] = 1;
				after.erase(*after.begin());
			} else if(before.size()) {
				done[*before.begin()] = 1;
				before.erase(*before.begin());
			} else {
				good = 0;
				break;
			}
			if(t[b[s]] > b[s] && !done[s]) before.insert(s);
		}
		cout << (good ? "Yes\n" : "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