Submission #1272693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272693		goulthen	Curtains (NOI23_curtains)	C++20	100 / 100	521 ms	137792 KiB

curtains

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

#define int long long
#define ll long long
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define per(i,a,b) for (int i = a; i >= b; i--)
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define all(v) (v).begin(), (v).end()

const int MAXN = 5e5+10;
const int INF = 1e18 + 5;
const int MOD = 1e9+7;

vector<int> tl[MAXN], tr[MAXN];
int closest[MAXN];

struct query {int l,r,id;};
int ans[MAXN];

void DC(int s, int e, vector<query> qrs) {
	if (qrs.empty()) return;
	if (s==e) {
		bool ok = 0;
		for (int x : tr[s]) if (x==e) ok = 1;
		for (query q : qrs) ans[q.id] = ok;
		return;
	}

	int m = (s+e)/2;

	vector<pii> stk;
	per(i,m,s) {
		int br = -1, ar = INF;
		for (int r : tr[i]) {
			if (r > e) continue;
			if (r>=m) ar=min(ar,r);
			else br = max(br, r);
		}

		closest[i] = INF;
		if(ar!=INF) closest[i] = min(closest[i],ar);
		while (!stk.empty()) {
			pii t = stk.back();
			if(t.fi <= br +1 || closest[i] <= t.se) {
				stk.pop_back();
				closest[i] = min(closest[i], t.se);
			} else break;
		}
		stk.push_back({i,closest[i]});

	}

	stk.clear();
	rep(i,m+1,e) {
		int bl = INF, al = -1;
		for (int l : tl[i]) {
			if (l < s) continue;
			if (l <= m+1) al = max(al,l);
			else bl = min(bl,l);
		}

		closest[i] = -1;
		if(al <= m+1) closest[i] = max(closest[i], al);

		while (!stk.empty()) {
			pii t = stk.back();
			if (bl-1 <= t.fi || closest[i] >= t.se) {
				stk.pop_back();
				closest[i] = max(closest[i], t.se);
			} else break;
		}
		stk.push_back({i,closest[i]});
	}

	vector<query> lq, rq;
	for (query q : qrs) {
		if (q.r <= m) lq.push_back(q);
		else if(q.l>m) rq.push_back(q);
		else {
			ans[q.id] = (closest[q.l] <= q.r && closest[q.r] >= q.l);
		}
	}

	DC(s,m,lq);
	DC(m+1,e, rq);
}

void solve() {
	int n,m,q;cin >> n >> m >> q;

	rep(i,1,m) {
		int l,r;cin >> l >> r;
		tr[l].pb(r);
		tl[r].pb(l);
	}

	vector<query> qrs;
	rep(i,1,q) {
		int l,r;cin >> l >> r;
		qrs.push_back({l,r,i});
	}

	DC(1,n,qrs);

	rep(i,1,q) {
		cout << (ans[i] ? "YES\n":"NO\n");	
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr);
	int tt = 1;
	//cin >> tt;

	while (tt--) solve();
	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