제출 #1141637

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141637		mendeke	Curtains (NOI23_curtains)	C++20	20 / 100	631 ms	77684 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, k = 300, t[N * 4], md[N * 4], q, a, b, c, l, r, L, R, ans[N];
vector <pair <pair <ll, ll>, ll>> v;
vector <ll> gl[N], gr[N];

bool cmp (pair <pair <ll, ll>, ll> a, pair <pair <ll, ll>, ll> b){
	if (a.F.F / k == b.F.F / k){
		return a.F.S < b.F.S;
	}
	return a.F.F < b.F.F;
}

void push (ll tl, ll tr, ll v){
	t[v] += md[v];
	if (tl != tr){
		md[v + v] += md[v];
		md[v + v + 1] += md[v];
	}
	md[v] = 0;
}

void upd (ll l, ll r, ll val, ll tl = 1, ll tr = n, ll v = 1){
	push (tl, tr, v);
	if (tr < l || tl > r){
		return;
	}
	if (l <= tl && tr <= r){
		md[v] += val;
		push (tl, tr, v);
		return;
	}
	ll tm = (tl + tr) / 2;
	upd (l, r, val, tl, tm, v + v);
	upd (l, r, val, tm + 1, tr, v + v + 1);
	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){
	push (tl, tr, v);
	if (tr < l || tl > r){
		return 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 >> l >> r;
		gl[l].pb (r);
		gr[r].pb (l);
	}
	for (int i = 1; i <= q; i++){
		cin >> l >> r;
		v.pb ({{l, r}, i});
	}
	sort (all (v), cmp);
	L = 1, R = 0;
	for (auto i: v){
		while (L > i.F.F){
			L--;
			for (auto y: gl[L]){
				if (y <= i.F.S)upd (L, y, 1);
			}
		}
		while (L < i.F.F){
			for (auto y: gl[L]){
				if (y <= R){
					upd (L, y, -1);
				}
			}
			L++;
		}
		while (R < i.F.S){
			R++;
			for (auto y: gr[R]){
				if (y >= i.F.F){
					upd (y, R, 1);
				}
			}
		}
		while (R > i.F.S){
			for (auto y: gr[R]){
				if (y >= L){
					upd (y, R, -1);
				}
			}
		}
		if (get (i.F.F, i.F.S) > 0){
			ans[i.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