제출 #1312955

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312955		samarthkulkarni	Curtains (NOI23_curtains)	C++20	0 / 100	1595 ms	17332 KiB

curtains

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

using ll = long long;
#define vi vector<long long>
#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];


struct Node {
	int mx, mn;
	Node() {mx = mn = -1;}
};
Node _merge(Node a1, Node a2) {
	a1.mx = max(a1.mx, a2.mx);
	a1.mn = min(a1.mn, a2.mn);
	return a1;
}
struct SegTree{
	vector<Node> tree;
	vi a, lzy;
	ll n;
	SegTree(ll _n) {
		n = _n+2;
		a.resize(n, -1);
		tree.resize(4*n);
		lzy.resize(4*n);
	}


	void push(int id, int l, int r) {
		if (!lzy[id]) return;

		tree[id].mx = tree[id].mn = lzy[id];

		if (l != r) {
			lzy[id<<1] = lzy[id];
			lzy[id<<1|1] = lzy[id];
		}
		lzy[id] = 0;
	}


	void update(int id, int l, int r, int a, int b) {
		push(id, l, r);
		int mx = tree[id].mx, mn = tree[id].mn;
		if (mx < a) return;
		if (mn >= a) {
			lzy[id] = b;
			push(id, l, r);
			return;
		}

		if (mn == mx) return;

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

		update(id<<1, l, mid, a, b);
		update(id<<1|1, mid+1, r, a, b);

		tree[id] = _merge(tree[id<<1], tree[id<<1|1]);
	}

	void pupd(int id, int l, int r, int pos, int val) {
		push(id, l, r);
		if (pos < l || pos > r) return;
		if (l == r) {
			tree[id].mx = tree[id].mn = val;
			a[l] = val;
			return; 
		}

		int mid = (l + r) >> 1;
		pupd(id<<1, l, mid, pos , val);
		pupd(id<<1|1, mid+1, r, pos, val);
		tree[id] = _merge(tree[id<<1], tree[id<<1|1]);
	}


	ll query(int id, int l, int r, int pos) {
		push(id, l, r);
		if (pos < l || pos > r) return -1;
		if (l == r) return tree[id].mx;

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

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


	void update(int a, int b) {update(1, 0, n-1, a, b);}
	void pupd(int pos, int val) {pupd(1, 0, n-1, pos, val);}
	ll 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]), greater<int>());
		sort(all(qw[i]), greater<pr>());
	}


	SegTree k(n);

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


	vi res(q);


	for (int i = 1; i <= n; i++) {
		int j = 0;
		for (auto [l, e] : qw[i]) {
			while (j < st[i].size() && st[i][j] >= l) {
				k.pupd(st[i][j], i);
				j++;
			}

			

			if (j > 0) {
				k.update(st[i][j-1]-1, i);
			}

			res[e] = (k.query(l) == i);
		}

		for (; j < st[i].size(); j++) k.pupd(st[i][j], i);


		if (j > 0) {
			k.update(st[i][j-1]-1, i);
		}


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

	}

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

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


}

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