Submission #1279478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279478		muhammad-ahmad	Curtains (NOI23_curtains)	C++20	100 / 100	1403 ms	234232 KiB

curtains

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

// #define int long long
#define endl '\n'

const int N = 5e5 + 5;

int n, m, q, ans[N], tans[N], tans1[N];
vector<int> L[N], R[N];
map<pair<int, int>, bool> CC;
vector<vector<int>> Temp;
deque<pair<int, int>> dq1, dq2;

void solve (vector<vector<int>> Q = Temp, int l = 1, int r = n){
	// cout << l << ' ' << r << endl;
	// for (auto i : Q){
		// cout << i[0] << ' ' << i[1] << endl;
	// }
	// cout << endl;
	if (Q.empty()){
		return;
	}
	
	if (r - l == 0){
		for (auto i : Q){
			ans[i[2]] = CC[{i[0], i[1]}];
		}
		return;
	}
	for (int i = l; i <= r; i++) tans[i] = 0;
	
	for (int i = (l + r) / 2; i >= l; i--){
		tans1[i] = -1;
		tans[i] = n + 1;
		for (auto j : L[i]){
			if (j >= (l + r) / 2) tans[i] = min(tans[i], j);
			else tans1[i] = max(tans1[i], j);
		}
		while (dq1.size()){
			if (!(tans1[i] < dq1.back().first - 1 && tans[i] > dq1.back().second)){
				tans[i] = min(tans[i], dq1.back().second);
				dq1.pop_back();
			}
			else break;
		}
		dq1.push_back({i, tans[i]});
	}
	
	// for (auto i : dq1){
		// cout << i.first << ' ' << i.second;
	// }
	
	for (int i = (l + r) / 2 + 1; i <= r; i++){
		tans1[i] = n + 1;
		tans[i] = -1;
		// cout << tans1[i] <<< ' ' << tans[i] << endl;

		for (auto j : R[i]){
			if ((l + r) / 2 >= j - 1) tans[i] = max(tans[i], j);
			else tans1[i] = min(tans1[i], j);
		}
		while (dq2.size()){
			if (!(tans1[i] > dq2.back().first + 1 && tans[i] < dq2.back().second)){
				tans[i] = max(tans[i], dq2.back().second);
				dq2.pop_back();
			}
			else break;
		}
		dq2.push_back({i, tans[i]});
	}
	
	// for (auto i : dq2){
		// cout << i.first << ' ' << i.second;
	// }
	

	vector<vector<int>> ll, rr;
	for (auto &i : Q){
		if (i[1] <= (l + r) / 2) ll.push_back(move(i));
		else if (i[0] > (l + r) / 2) rr.push_back(move(i));
		else {
			int LL = i[0], RR = i[1];
			ans[i[2]] = (tans[LL] <= RR && tans[RR] >= LL);
		}
	}
	
	// cout << ans[1] << ' ' << ans[2] << endl;
	
	dq1.clear(), dq2.clear();
	solve(ll, l, (l + r) / 2);
	solve(rr, (l + r) / 2 + 1, r);
}

int main(){
	// int n, m, q;
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++){
		int l, r; cin >> l >> r;
		R[r].push_back(l);
		L[l].push_back(r);
		CC[{l, r}] = 1;
	}
	// cout << CC[{10, 10}] << endl;
	// for (int i = 1; i <= n; i++) cout << L[i].size() << ' ' << R[i].size() << endl;
	// cout << endl;
	
	for (int i = 1; i <= q; i++){
		int l, r; cin >> l >> r;
		Temp.push_back({l, r, i});
	}
	
	// for (auto i : Temp) cout << i.first << ' ' << i.second << endl;
	// cout << endl;
	
	solve();
	for (int i = 1; i <= q; i++) {
		// cout << ans[i] << ' ';
		if (ans[i]) cout << "YES";
		else cout << "NO";
		cout << endl;
	}
	// cout << 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