Submission #1313220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313220		samarthkulkarni	Curtains (NOI23_curtains)	C++20	24 / 100	1597 ms	37176 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 mx, mn, lzy;
	Node() {mx = -1, mn = -1, lzy = 0;}
};

Node tree[N<<2];


struct SegTree{
	ll n;
	SegTree(ll _n) {
		n = _n+2;
	}

	void update(int id, int l, int r, int L, int R, int a, int b) {
		if (tree[id].lzy) {
        	tree[id].mx = tree[id].mn = tree[id].lzy;
        	if (l != r) {
            	tree[id<<1].lzy = tree[id].lzy;
            	tree[id<<1|1].lzy = tree[id].lzy;
        	}
        	tree[id].lzy = 0;
    	}


		if (tree[id].mx < a) return;

		if (L > r || l > R) return;

		
		if (L <= l && R >= r && tree[id].mn >= a) {
			tree[id].mx = tree[id].mn = b;
			if (l != r) {
           		tree[id<<1].lzy = b;
           		tree[id<<1|1].lzy = b;
       		}
    		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].mx = max(tree[id<<1].mx, tree[id<<1|1].mx);
		tree[id].mn = min(tree[id<<1].mn, tree[id<<1|1].mn);
	}

	void pupd(int id, int l, int r, int pos, int val) {
		if (tree[id].lzy) {
        	tree[id].mx = tree[id].mn = tree[id].lzy;
        	if (l != r) {
            	tree[id<<1].lzy = tree[id].lzy;
            	tree[id<<1|1].lzy = tree[id].lzy;
        	}
        	tree[id].lzy = 0;
    	}


		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].mx = max(tree[id<<1].mx, tree[id<<1|1].mx);
		tree[id].mn = min(tree[id<<1].mn, tree[id<<1|1].mn);
	}


	ll query(int pos) {
		int id = 1;
		int l = 0, r = n-1;
		while (l < r) {
			if (tree[id].lzy) {
        		tree[id].mx = tree[id].mn = tree[id].lzy;
        		if (l != r) {
            		tree[id<<1].lzy = tree[id].lzy;
            		tree[id<<1|1].lzy = tree[id].lzy;
        		}
        		tree[id].lzy = 0;
    		}

    		int mid = (l+r)>>1;
    		id <<=1;
    		if (pos <= mid) {
    			r = mid;
    		} else {
    			id++;
    			l = mid+1;
    		}
		}


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


    	return tree[id].mx;

	}


	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);}
};




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});
	}



	SegTree k(n);
	vi res(q);

	for (int i = 1; i <= n; i++) {

		for (auto l : st[i]) {
			k.pupd(l, i);
			k.update(1, l, l-1, i);
		}

		for (auto [l, e] : qw[i])  {
			res[e] = (k.query(l) == 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