Submission #933210

#	Time	Username	Problem	Language	Result	Execution time	Memory
933210		zhaohaikun	Curtains (NOI23_curtains)	C++17	100 / 100	608 ms	74580 KiB

curtains

#include <bits/stdc++.h>
#define mid ((l + r) >> 1)
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
const int N = 5e5 + 10;
int n, m, q;
vector <int> v[N];
int info[N << 2], tag[N << 2];
void down(int num, int x) {
	chkmax(tag[num], x);
	chkmax(info[num], x);
}
void pushdown(int num) {
	if (tag[num]) down(ls, tag[num]), down(rs, tag[num]), tag[num] = 0;
}
void pushup(int num) {
	info[num] = min(info[ls], info[rs]);
}
void change(int num, int l, int r, int L, int R, int x) {
	if (L <= l && r <= R) return down(num, x);
	pushdown(num);
	if (mid >= L) change(li, L, R, x);
	if (mid < R) change(ri, L, R, x);
	pushup(num);
}
int query(int num, int l, int r, int L, int R) {
	if (L <= l && r <= R) return info[num];
	pushdown(num);
	if (mid >= R) return query(li, L, R);
	if (mid < L) return query(ri, L, R);
	return min(query(li, L, R), query(ri, L, R));
}
bool ans[N];
vector <pair <int, int>> qq[N];
signed main() {//antirrhinum
//	freopen("antirrhinum.in", "r", stdin);
//	freopen("antirrhinum.out", "w", stdout);
	read(n), read(m), read(q);
	F(i, 1, m) {
		int l, r; read(l), read(r);
		v[r].push_back(l);
	}
	F(i, 1, q) {
		int l, r; read(l), read(r);
		qq[r].emplace_back(l, i);
	}
	F(i, 1, n) {
		for (int j: v[i]) change(1, 1, n, j, i, j);
		for (auto [a, b]: qq[i]) ans[b] = query(1, 1, n, a, i) >= a;
	}
	F(i, 1, q) puts(ans[i] ? "YES" : "NO");
	return 0;
}

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