Submission #1100069

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100069		NoMercy	Curtains (NOI23_curtains)	C++17	100 / 100	733 ms	55872 KiB

curtains

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int inf = 1e9 + 199;

#define left v + 1
#define right v + 2 * (mid - l)
struct Lazy_Segree {
	struct pi {
		int mn = 0, lazy = 0, mark = 0;
	} emp;
	vector<pi> tree;
	void init (int x) {
		tree.assign (x << 1, emp);
	}

	void push (int v, int l, int r) {
		if (tree[v].mark == 0 || l == r) return;
		int mid = (l + r) >> 1;
		tree[left].mn = max(tree[left].mn, tree[v].lazy);
		tree[right].mn = max(tree[right].mn, tree[v].lazy);
		tree[left].lazy = max(tree[left].lazy, tree[v].lazy);
		tree[right].lazy = max(tree[right].lazy, tree[v].lazy);
		tree[v].mark = tree[v].lazy = 0;
		tree[left].mark = tree[right].mark = 1;
	}
	void update (int v, int l, int r, int ml, int mr, int val) {
		if (l == r || l >= mr || ml >= r) return;
		if (ml <= l && r <= mr) {
			tree[v].mn = max(tree[v].mn, val);
			tree[v].lazy = max(tree[v].lazy, val);
			tree[v].mark = 1;
			return;
		}
		push (v, l, r);
		int mid = (l + r) >> 1;
		update (left, l, mid, ml, mr, val);
		update (right, mid, r, ml, mr, val);
		tree[v].mn = min(tree[left].mn, tree[right].mn);
	}
	int get (int v, int l, int r, int ml, int mr) {
		if (l == r || l >= mr || ml >= r) return inf;
		if (ml <= l && r <= mr) {
			return tree[v].mn;
		}
		push (v, l, r);
		int mid = (l + r) >> 1;
		return min(get (left, l, mid, ml, mr), get (right, mid, r, ml, mr));
	}
};

int32_t main () {

	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 

	int N, M, Q;
	cin >> N >> M >> Q;
	vector<array<int, 2>> all;
	for (int i = 0;i < M;i ++) {
		int l, r;
		cin >> l >> r;
		all.push_back({l, r});
	}
	vector<array<int, 3>> q;
	for (int i = 0;i < Q;i ++) {
		int l, r;
		cin >> l >> r;
		q.push_back({l, r, i});
	}
	sort(q.begin(), q.end(), [&](array<int, 3> a, array<int, 3> b) {
		return (a[1] < b[1]);
	});
	sort(all.begin(), all.end(), [&](array<int, 2> a, array<int, 2> b) {
		return (a[1] < b[1]);
	});

	Lazy_Segree LS;
	LS.init (N + 1);
	
	string res[Q];
	int ind = 0;
	// cout << "\n";
	for (int i = 0;i < Q;i ++) {
		// cout << q[i][0] << " " << q[i][1] << "\n";
		while (ind < M && all[ind][1] <= q[i][1]) {
			LS.update (1, 1, N + 1, all[ind][0], all[ind][1] + 1, all[ind][0]);
			ind ++;
		}
		if (LS.get (1, 1, N + 1, q[i][0], q[i][1] + 1) >= q[i][0]) {
			res[q[i][2]] = "YES";
		} else {
			res[q[i][2]] = "NO";
		}
	}
	for (int i = 0;i < Q;i ++) {
		cout << res[i] << "\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