Submission #1312830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312830		samarthkulkarni	Curtains (NOI23_curtains)	C++20	0 / 100	3 ms	2360 KiB

curtains

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

using ll = long long;
#define vi vector<long long>
#define all(x) x.begin(), x.end()
#define endl "\n"
#define pr pair<ll, ll>
#define ff first
#define ss second

void solution();
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solution();
    return 0;
}


const int N = 5e5+10;
const int K = 25;
int nxt[N];
pr a[N];
int BL[N][K];

void solution() {
	ll n, m, q;
	cin >> n >> m >> q;

	for (int i = 0; i < m; i++) cin >> a[i].ff >> a[i].ss;

	// sort(a, a+m);
	
	vi qw(n+1, 1e9);

	for (ll i = 0; i < m; i++) {
		qw[a[i].ff] = min(qw[a[i].ff], i);
	}


	iota(nxt, nxt+N, 0);

	for (int i = 0; i < m; i++) {
		ll mx = 1e9;
		for (int j = 0; j < m; j++) {
			if (j == i) continue;
			if (a[j].ff <= a[i].ss+1 && a[j].ff >= a[i].ff && a[j].ss >= a[i].ss) {
				if (mx > a[j].ss) {
					mx = a[j].ss;
					nxt[i] = j;
				}
			} 
		}
	}





	for (int j = 0; j < K; j++) {
		for (int i = 0; i < m; i++) {
			if (BL[i][j] == 0) {BL[i][j] = nxt[i]; continue;}
			BL[i][j] = BL[BL[i][j-1]][j-1];
		}
	}


	auto cal = [&](int l, int r) {
		int k = qw[l];
		for (int j = K-1; j >= 0; j--) {
			if (a[BL[k][j]].ss <= r) {
				k = BL[k][j];
			}
		}

		return a[k].ss == r;
	};



	while (q--) {
		int l, r;
		cin >> l >> r;

 
		if (qw[l] == 1e9) {
			cout << "NO" << endl;
			continue;
		}


		if (cal(l, r)) {cout << "YES" << endl;}
		else cout << "NO" << endl;

	}

	


	

}

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