제출 #1312474

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1312474		sakuda00	Curtains (NOI23_curtains)	C++20	100 / 100	1477 ms	65496 KiB

curtains

#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <queue>
#include <deque>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
using ll = long long;
int inf = (int)1e9;
void chmin(int& a, int b) {
	a = min(a, b);
}
struct SegTree {
	int n, N;
	vector<int> dat, lazy;
	int E = inf;
	SegTree(int M) {
		int x = 0;
		while ((1 << x) < M) x++;
		n = (1 << x);
		N = 2 * n;
		dat.assign(N, inf);
		lazy.assign(N, inf);
	}
	int left(int k) {
		return ((2*k) + 1);
	}
	int right(int k) {
		return ((2*k) + 2);
	}
	void eval(int k) {
		if (k < n-1) {
			chmin(lazy[left(k)], lazy[k]);
			chmin(lazy[right(k)], lazy[k]);
		}
		chmin(dat[k], lazy[k]);
		lazy[k] = inf;
	}
	void update(int a, int b, int x, int k, int l, int r) {
		eval(k);
		if (b <= l or r <= a) return;
		if (a <= l and r <= b) {
			chmin(lazy[k], x);
			eval(k);
			return;
		}
		update(a, b, x, left(k), l, (l+r)/2);
		update(a, b, x, right(k), (l+r)/2, r);
		dat[k] = max(dat[left(k)], dat[right(k)]);
	}
	void update(int l, int r, ll x) {
		update(l, r,  x, 0, 0, n);
	}
	int query(int a, int b, int k, int l, int r) {
		
		eval(k);
		if (b <= l or r <= a) return -inf;
		if (a <= l and r <= b) {
			return dat[k];
		}
		return max(query(a, b, left(k), l, (l+r)/2), query(a, b, right(k), (l+r)/2, r));
	}
	int query(int l, int r) {
		return query(l, r, 0, 0, n);
	}
};
int main() {
	int N, M, Q;cin >> N >> M >> Q;
	vector<vector<int>> IN(N + 1);
	for (int i = 0;i < M;i++)  {
		int l, r;cin >> l >> r;
		IN[l].push_back(r);
	}
	vector<int> S(Q), E(Q);
	vector<vector<int>> QRY(N + 1);
	for (int i = 0;i < Q;i++) {
		cin >> S[i] >> E[i];
		QRY[S[i]].push_back(i);
	}
	SegTree SEG(N + 1);
	vector<int> res(Q, false);
	for (int i = N;i >= 1;i--) {
		for (int r : IN[i]) {
			SEG.update(i, r +1, r);

		}
		for (auto id : QRY[i]) {
			int mx = SEG.query(S[id], E[id] + 1);
			//cout << i << " " << mx << endl;
			if (mx <= E[id]) {
				res[id] = true;
			}
		}
	}
	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: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20