제출 #1137182

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1137182		mendeke	Curtains (NOI23_curtains)	C++20	20 / 100	720 ms	49496 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;
vector <pair <ll, ll>> v[N];
pair <ll, ll> p[N];

ll binpow (ll a, ll b){a %= mod;if (b == 0){return 1;}else if (b % 2 == 1){return binpow (a, b - 1) % mod * a % mod;}else{ll t = binpow (a, b / 2) % mod;return t * t % mod;}}

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;
	}
	sort (p + 1, p + m + 1);
	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){
			b++;
		}
		b--;
//		if (p[b].S != i){
//			continue;
//		}
		for (auto y: v[i]){
			if (a <= y.F){
				l = 1, r = b, res = b;
				while (l <= r){
					ll md = (l + r) / 2;
					if (p[md].F <= y.F){
						res = md;
						l = md + 1;
					}
					else{
						r = md - 1;
					}
				}
				if (p[res].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