Submission #1137205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137205		mendeke	Curtains (NOI23_curtains)	C++20	20 / 100	990 ms	66812 KiB

curtains

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(), x.end()

const int mod = 1e9 + 7;
const int N = 500001;

using namespace std;

ll n, m, q, a, b, c, d, t[N * 4], l, r, ans[N], res, mx[N];
set <ll> s;
vector <pair <ll, ll>> v[N];
pair <ll, ll> p[N];

void upd (ll idx, ll val, ll tl = 1, ll tr = n, ll v = 1){
	if (tl == tr){
		t[v] = val;
		return;
	}
	ll tm = (tl + tr) / 2;
	if (tm < idx){
		upd (idx, val, tm + 1, tr, v + v + 1);
	}
	else{
		upd (idx, val, tl, tm, v + v);
	}
	t[v] = min (t[v + v], t[v + v + 1]);
}

ll get (ll l, ll r, ll tl = 1, ll tr = n, ll v = 1){
	if (tr < l || tl > r){
		return n + 1;
	}
	if (l <= tl && tr <= r){
		return t[v];
	}
	ll tm = (tl + tr) / 2;
	return min (get (l, r, tl, tm, v + v), get (l, r, tm + 1, tr, v + v + 1));
}

signed main (){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++){
		cin >> p[i].F >> p[i].S;
		mx[p[i].S] = max (mx[p[i].S], p[i].F);
		swap (p[i].F, p[i].S);
	}
	sort (p + 1, p + m + 1);
	for (int i = 1; i <= m; i++){
		swap (p[i].F, p[i].S);
	}
	for (int i = 0; i <= n; i++){
		upd (i, n + 1);
	}
	for (int i = 1; i <= m; i++){
		if (get (p[i].S, p[i].S) == n + 1){
			upd (p[i].S, p[i].F);
		}
		upd (p[i].S, get (p[i].F - 1, p[i].S));
	}
	for (int i = 1; i <= q; i++){
		cin >> l >> r;
		v[r].pb ({l, i});
	}
	b = 1;
	p[m + 1].S = n + 1;
	for (int i = 1; i <= n; i++){
		a = get (i, i);
		while (p[b].S <= i){
			s.insert (p[b].F);
			b++;
		}
		for (auto y: v[i]){
			if (y.F <= mx[i] && a <= y.F && s.size() && s.lower_bound (y.F) != s.end() && *s.lower_bound (y.F) == y.F){
				ans[y.S] = 1;
			}
		}
	}
	for (int i = 1; i <= q; i++){
		if (ans[i]){
			cout << "YES\n";
		}
		else{
			cout << "NO\n";
		}
	}
}

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