Submission #1146650

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146650		am_aadvik	Curtains (NOI23_curtains)	C++20	100 / 100	620 ms	29776 KiB

curtains

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
const int inf = 1e9;
using namespace std;

class segtree {
private:
	vector<int> st, lazy, a;
	const int dv = inf;
	const int ldv = 0;

	void upd(int s, int e, int node, int val) {
		if (val == ldv) return;
		st[node] = max(val, st[node]);
	}

	int build(int s, int e, int node) {
		if (s == e)
			return st[node] = a[s];
		int mid = (s + e) / 2;
		return st[node] = min(build(s, mid, node * 2), build(mid + 1, e, node * 2 + 1));
	}

	void update(int s, int e, int node, int l, int r, int val) {
		if ((s > r) || (e < l))
			return;
		if ((l <= s) && (r >= e)) {
			upd(s, e, node, val);
			lazy[node] = max(lazy[node], val);
			return;
		}

		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] = max(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = max(lazy[node * 2 + 1], lazy[node]);
		lazy[node] = ldv;

		update(s, mid, node * 2, l, r, val);
		update(mid + 1, e, node * 2 + 1, l, r, val);
		st[node] = min(st[node * 2], st[node * 2 + 1]);
	}

	int query(int s, int e, int node, int l, int r) {
		if ((s > r) || (e < l))
			return dv;
		if ((l <= s) && (r >= e))
			return st[node];

		int mid = (s + e) / 2;
		upd(s, mid, node * 2, lazy[node]);
		upd(mid + 1, e, node * 2 + 1, lazy[node]);
		lazy[node * 2] = max(lazy[node * 2], lazy[node]);
		lazy[node * 2 + 1] = max(lazy[node * 2 + 1], lazy[node]);
		lazy[node] = ldv;

		return min(query(s, mid, node * 2, l, r), query(mid + 1, e, node * 2 + 1, l, r));
	}

public:
	segtree(int n) {
		a.assign(n, 0);
		st.resize(4 * n, 0);
		lazy.resize(4 * n, 0);
		//build(0, n - 1, 1);
	}

	int query(int l, int r) {
		return query(0, a.size() - 1, 1, l, r);
	}

	void update(int l, int r, int val) {
		update(0, a.size() - 1, 1, l, r, val);
	}
};

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m, q; cin >> n >> m >> q;
	vector<bool> res(q);
	vector<pair<int, int>> a(m);
	vector<pair<pair<int, int>, int>> arr(q);
	for (int i = 0; i < m; ++i)
		cin >> a[i].second >> a[i].first;
	sort(a.begin(), a.end());

	for (int i = 0; i < q; ++i) {
		cin >> arr[i].first.second >> arr[i].first.first;
		arr[i].second = i;
	}
	sort(arr.begin(), arr.end());

	int j = 0;
	segtree st(n + 1);
	for (auto x : arr) {
		int s = x.first.second, e = x.first.first;
		while ((j < a.size()) && (a[j].first <= e))
			st.update(a[j].second, a[j].first, a[j].second),
			++j;
		res[x.second] = (st.query(s, e) >= s);
	}

	for (auto x : res)
		cout << (x ? "YES" : "NO") << '\n';
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20