제출 #1313080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313080		samarthkulkarni	Curtains (NOI23_curtains)	C++20	24 / 100	1596 ms	29364 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 mx[N<<2], mn[N<<2];
int lzy[N<<2];
int pi[N];


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 (lzy[id]) {
        	mx[id] = mn[id] = lzy[id];
        	if (l != r) {
            	lzy[id<<1] = lzy[id];
            	lzy[id<<1|1] = lzy[id];
        	}
        	lzy[id] = 0;
    	}

		if (mx[id] < a) return;

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

		mx[id] = max(mx[id<<1], mx[id<<1|1]);
		mn[id] = min(mn[id<<1], mn[id<<1|1]);
	}

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


		if (pos < l || pos > r) return;
		if (l == r) {
			mx[id] = mn[id] = 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);


		mx[id] = max(mx[id<<1], mx[id<<1|1]);
		mn[id] = min(mn[id<<1], mn[id<<1|1]);
	}


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

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


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


    	return mx[id];

	}


	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;

	memset(mx, -1, sizeof(mx));
	memset(mn, -1, sizeof(mn));


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

			if (pi[l] != i) pi[l] = k.query(l);

			res[e] = (pi[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