Submission #1313276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313276		samarthkulkarni	Curtains (NOI23_curtains)	C++17	100 / 100	800 ms	76392 KiB

curtains

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

using ll = int;
#define vi vector<int>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}



const int N = 5e5+10;
vi st[N];
vector<pr> qw[N];
int pi[N];

struct Node {
	int val, lz_l, lz_r;
	Node() {val = 0, lz_l = -1, lz_r = -1;}
};


Node tree[N<<2];
struct SegTree {
	ll n;
	SegTree (ll _n) {
		n = _n+2;
	}

	void build(int id, int l, int r) {
		if (l == r) {
			tree[id].val = l-1;
			return;
		}

		int mid = (l+r) >> 1;
		build(id<<1, l, mid);
		build(id<<1|1, mid+1, r);
	}

	inline void push(int id, int l, int r) {
		if (tree[id].lz_l == -1) return;

		if (l == r) {
			if (tree[id].val >= tree[id].lz_l) tree[id].val = tree[id].lz_r;
		} else {
			if (tree[id<<1].lz_l == -1) {
				tree[id<<1].lz_l = tree[id].lz_l;
				tree[id<<1].lz_r = tree[id].lz_r;
			} else if (tree[id<<1].lz_r >= tree[id].lz_l) {
				tree[id<<1].lz_l = min(tree[id<<1].lz_l, tree[id].lz_l);
				tree[id<<1].lz_r = tree[id].lz_r;
			}


			if (tree[id<<1|1].lz_l == -1) {
				tree[id<<1|1].lz_l = tree[id].lz_l;
				tree[id<<1|1].lz_r = tree[id].lz_r;
			}else if (tree[id<<1|1].lz_r >= tree[id].lz_l) {
				tree[id<<1|1].lz_l = min(tree[id<<1|1].lz_l, tree[id].lz_l);
				tree[id<<1|1].lz_r = tree[id].lz_r;
			}
		}

		tree[id].lz_l = tree[id].lz_r = -1;
	}


	void update(int id, int l, int r, int L, int R, int a, int b) {
		push(id, l, r);
		if (l > R || L > r) return;
		if (L <= l && R >= r) {
			tree[id].lz_l = a;
			tree[id].lz_r = b;
			push(id, l, r);
			return;
		}

		int mid = (l + r) >> 1;
		update(id<<1, l, mid, L, R, a, b);
		update(id<<1|1, mid+1, r, L, R, a, b);
	}


	int query(int id, int l, int r, int pos) {
		push(id, l, r);
		if (l == r) return tree[id].val;

		int mid = (l + r) >> 1;

		if (pos <= mid) return  query(id<<1, l, mid, pos);
		return query(id<<1|1, mid+1, r, pos);
	}



	void build() {build(1, 0, n-1);}
	void update(int l, int r, int a, int b) {update(1, 0, n-1, l, r, a, b);}
	int query(int pos) {return query(1, 0, n-1, pos);}
};



void solution() {
	ll n, m, q;
	cin >> n >> m >> q;



	for (int i = 0; i < m; i++) {
		int l, r; cin >> l >> r;
		st[r].push_back(l);
	}

	for (int i = 0; i < q; i++) {
		int l, r; cin >> l >> r;
		qw[r].push_back({l, i});
	}


	// for (int i = 1; i <= n; i++) {
	// 	sort(all(st[i]));
	// }


	SegTree k(n);
	k.build();

	vi res(q);

	for (int i = 1; i <= n; i++) {
		for (auto l : st[i]) {
			k.update(1, l, l-1, i);
		}

		// cout << i << endl;

		// for (int j = 1; j <= n; j++) {
		// 	cout << k.query(j) << " ";
		// }
		// cout << endl << endl;

		for (auto [l, e] : qw[i]) {
			res[e] = (k.query(l) == i);
		}
	}


	for (auto i : res) {
		cout << (i?"YES":"NO") << endl;
	}

}

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