제출 #886058

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
886058		vjudge1	Curtains (NOI23_curtains)	C++17	100 / 100	798 ms	73132 KiB

curtains

#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
using namespace std;

struct LazySegtree {
	vector <int> t, lt;
	int n;
	void init(int size) {
		n = size;
		t = lt = vector<int>(n * 4, inf);
	}
	void push(int v) {
		// sol için
		t[v * 2] = min(t[v * 2], lt[v]);
		lt[v * 2] = min(lt[v * 2], lt[v]);
		// sağ için
		t[v * 2 + 1] = min(t[v * 2 + 1], lt[v]);
		lt[v * 2 + 1] = min(lt[v * 2 + 1], lt[v]);
		lt[v] = inf;
	}
	void update(int v, int l, int r, int ql, int qr, int val) {
		if(l >= ql and r <= qr) {
			t[v] = min(t[v], val);
			lt[v] = min(lt[v], val);
			return;
		}
		push(v);
		int m = (l + r) / 2;
		if(ql <= m) {
			update(v * 2, l, m, ql, qr, val);
		}
		if(qr > m) {
			update(v * 2 + 1, m + 1, r, ql, qr, val);
		}
		t[v] = max(t[v * 2], t[v * 2 + 1]);
	}
	int query(int v, int l, int r, int ql, int qr) {
		if(l >= ql and r <= qr) {
			return t[v];
		}
		push(v);
		int ans = 0;
		int m = (l + r) / 2;
		if(ql <= m) {
			ans = max(ans, query(v * 2, l, m, ql, qr));
		}
		if(qr > m) {
			ans = max(ans, query(v * 2 + 1, m + 1, r, ql, qr));
		}
		return ans;
	}
};

int32_t main(){
	fast
	int n, m, q;
	cin >> n >> m >> q;
	vector <pair<int, int> > cur;
	vector <array<int, 3> > qq;
	for(int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		cur.push_back({a, b});
	}
	for(int i = 0; i < q; i++) {
		int a, b;
		cin >> a >> b;
		qq.push_back({a, b, i});
	}
	sort(cur.begin(), cur.end());
	sort(qq.begin(), qq.end());
	reverse(cur.begin(), cur.end());
	reverse(qq.begin(), qq.end());
	bitset <500000> ans;
	int p = 0;
	LazySegtree st;
	st.init(n + 1);
	for(int i = 0; i < q; i++) {
		int ql = qq[i][0], qr = qq[i][1], qi = qq[i][2];
		while(ql <= cur[p].first and p < m) {
			// update segt for ul, ur
			int ul = cur[p].first, ur = cur[p].second;
			st.update(1, 1, n, ul, ur, ur);
			p++;
		}
		// direk range maxın <= qr olup olması
		ans[qi] = qr == st.query(1, 1, n, ql, qr);
	}
	for(int i = 0; i < q; i++) {
		cout << (ans[i] ? "YES" : "NO") << "\n";
	}
}

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