Submission #1214655

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214655		trimkus	Gift Exchange (JOI24_ho_t4)	C++20	100 / 100	1524 ms	74920 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;


struct RMQ {
	int n;
	int mn;
	vector<int> tree, lz;
	void init(int n, bool gr) {
		this->n = n;
		mn = (gr ? -(n / 2 + 1) : 0);
		tree = vector<int>(4 * n, mn);
		lz = vector<int>(4 * n, mn);
	}
	void push(int i) {
		for (int x : {i * 2, i * 2 + 1}) {
			tree[x] = max(tree[x], lz[i]);
			lz[x] = max(lz[x], lz[i]);
		}
		lz[i] = mn;
	}
	void update(int i, int l, int r, int ql, int qr, int d) {
		if (l > qr || r < ql) return;
		if (ql <= l && r <= qr) {
			tree[i] = max(tree[i], d);
			lz[i] = max(lz[i], d);
			return;
		}
		push(i);
		int m = (l + r) / 2;
		update(i * 2, l, m, ql, qr, d);
		update(i * 2 + 1, m + 1, r, ql, qr, d);
		tree[i] = max(tree[i * 2], tree[i * 2 + 1]);
	}
	void update(int ql, int qr, int d) {
		update(1, 1, n, ql, qr, d);
	}
	int query(int i, int l, int r, int ql, int qr) {
		if (l > qr || r < ql) return mn;
		if (ql <= l && r <= qr) {
			return tree[i];
		}
		push(i);
		int m = (l + r) / 2;
		return max(query(i * 2, l, m, ql, qr), query(i * 2 + 1, m + 1, r, ql, qr));
	}
	int query(int ql, int qr) {
		return query(1, 1, n, ql, qr);
	}
};

struct Fenwick {
	int n;
	vector<int> bit;
	Fenwick(int n) {
		this->n = 2 * n;
		bit = vector<int>(2 * n + 2);
	}
	void update(int i, int delta) {
		for (i += 1; i <= n; i += i & -i) {
			bit[i] += delta;
		}
	}
	void update(int l, int r, int delta) {
		update(l, delta);
		update(r + 1, -delta);
	}
	int query(int r) {
		int res = 0;
		for (r += 1; r > 0; r-= r & -r) {
			res += bit[r];
		}
		return res;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<int> a(n + 1), b(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; ++i) {
		cin >> b[i];
	}
	RMQ seg;
	seg.init(2 * n, false);
	vector<int> left(n + 1), right(n + 1);
	for (int i = 1; i <= n; ++i) {
		int l = seg.query(b[i], a[i]) + 1;
		left[i] = l;
		seg.update(b[i], a[i], i);
	}
	seg.init(2 * n, true);
	for (int i = n; i >= 1; --i) {
		int r = seg.query(b[i], a[i]);
		if (r == 0) r = n + 1;
		else r = -r;
		right[i] = r;
		seg.update(b[i], a[i], -i);
		//~ cerr << seg.query(1, 2 * n) << "\n";
	}
	Fenwick tree(n);
	vector<vector<int>> events(n + 2);
	for (int i = 1; i <= n; ++i) {
		events[right[i]].push_back(-i);
	}
	int q;
	cin >> q;
	vector<int> res(q);
	vector<int> ql(q), qr(q);
	for (int i = 0; i < q; ++i) {
		cin >> ql[i] >> qr[i];
		events[qr[i]].push_back(i);
	}
	//~ cout << "Intervals:\n";
	//~ for (int i = 1; i <= n; ++i) {
		//~ cout << left[i] << " " << right[i] << "\n";
	//~ }
	for (int i = 1; i <= n; ++i) {
		tree.update(left[i], i, +1);
		for (auto& j : events[i]) {
			if (j < 0) {
				tree.update(left[-j], -j, -1);
			} else {
				res[j] = tree.query(ql[j]);
			}
		}
		
	}
	for (int i = 0; i < q; ++i) {
		cout << (res[i] > 0 ? "No\n" : "Yes\n");
	}
}

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