Submission #1313072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313072		samarthkulkarni	Curtains (NOI23_curtains)	C++20	24 / 100	1597 ms	29532 KiB

curtains

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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];


struct Node {
	int mx, mn;
	Node() {
		mx = -1;
		mn = -1;
	}
};
inline Node _merge(Node a1, Node a2) {
	a1.mx = max(a1.mx, a2.mx);
	a1.mn = min(a1.mn, a2.mn);
	return a1;
}

Node tree[N<<2];
int lzy[N<<2];
struct SegTree{
	ll n;
	SegTree(ll _n) {
		n = _n+2;
	}
	inline 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 L, int R, int a, int b) {
		push(id, l, r);
		if (tree[id].mx < a) return;

		if (L > r || l > R) return;
		if (L <= l && R >= r) {
			if (tree[id].mn >= a) {
				lzy[id] = 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);
		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;
			return; 
		}
		int mid = (l + r) >> 1;
		if (pos <= mid) pupd(id<<1, l, mid, pos, val);
		else 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 l, int r, int a, int b) {update(1, 0, n-1,l, r, 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(qw[i]), greater<pr>());
		sort(all(st[i]), greater<int>());
	}


	SegTree k(n);
	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);
				k.update(1, st[i][j], st[i][j]-1, i);
				j++;
			}
			res[e] = (k.query(l) == i);
		}

		for (; j < st[i].size(); j++) {
			k.pupd(st[i][j], i);
			k.update(1, st[i][j], st[i][j]-1, i);
		}
	}


	for (int i = 0; i < q; i++) {
		cout << (res[i]?"YES":"NO") << endl;
	}


}

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