Submission #1368959

#TimeUsernameProblemLanguageResultExecution timeMemory
1368959gohchingjaykCurtains (NOI23_curtains)C++20
100 / 100
673 ms62192 KiB
#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
#define int ll

using ii = pair<int, int>;
using iii = pair<ii, int>;

constexpr int MAXN = 500'000 + 5;
constexpr int INF = 1e18 + 5;
constexpr int LOG = 20;

signed main() {
	cin.tie(nullptr)->sync_with_stdio(false); cout.tie(nullptr);

	int N, M, Q; cin >> N >> M >> Q;
	vector<int> FST(2 * N, -1);
	
	auto rmaxq = [&](int a, int b) {
		a += N; b += N + 1;
		int ans = -1;
		for (; a < b; a >>= 1, b >>= 1) {
			if (a & 1) ans = max(ans, FST[a++]);
			if (b & 1) ans = max(ans, FST[--b]);
		}
		return ans;
	};
	
	auto pupd = [&](int p, int v) {
		p += N;
		for (; p > 0; p >>= 1) FST[p] = max(FST[p], v);
	};
	
	vector<vector<int>> ranges_ending(N+1);
	vector<vector<ii>> queries_ending(N+1);

	// We want to query and save ranges as [a, b).
	for (int i = 0; i < M; ++i) {
		int a, b; cin >> a >> b;
		a--;
		ranges_ending[b].emplace_back(a);
	}
	
	for (int i = 0; i < Q; ++i) {
		int a, b; cin >> a >> b;
		a--;
		queries_ending[b].emplace_back(a, i);
	}
	
	vector<bool> answers(Q);
	
	for (int i = 0; i <= N; ++i) {
		for (int s : ranges_ending[i]) pupd(s, i);
		for (auto [s, q] : queries_ending[i]) {
			while (true) {
				int pa = FST[s + N];
				int re = rmaxq(s, pa);
				if (pa != re) pupd(s, re);
				else break;
			}
			
			answers[q] = FST[s + N] == i;
		}
	}
	
	for (int i = 0; i < Q; ++i) {
		cout << (answers[i] ? "YES" : "NO") << '\n';
	}
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...