Submission #1141666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141666		mendeke	Curtains (NOI23_curtains)	C++20	0 / 100	1597 ms	31924 KiB

curtains

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
#define ll int
#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 <pair <ll, 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, 0});
		gr[r].pb ({l, 0});
	}
	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){
		a = L;
		while (L > i.F.F){
			L--;
			for (int y = 0; y < gl[L].size(); y++){
				if (gl[L][y].F <= i.F.S && gl[L][y].S == 0)upd (L, gl[L][y].F, 1), gl[L][y].S = 1;
			}
		}
		while (L < i.F.F){
			for (int y = 0; y < gl[L].size(); y++){
				if (gl[L][y].S == 1){
					gl[L][y].S = 0;
					upd (L, gl[L][y].F, -1);
				}
			}
			L++;
		}
		while (R < i.F.S){
			R++;
			for (int y = 0; y < gr[R].size(); y++){
				if (gr[R][y].F >= i.F.F && gr[R][y].S == 0){
					gr[R][y].S = 1;
					upd (gr[R][y].F, R, 1);
				}
			}
		}
		while (R > i.F.S){
			for (int y = 0; y < gr[R].size(); y++){
				if (gr[R][y].S == 1){
					gr[R][y].S = 0;
					upd (gr[R][y].F, R, -1);
				}
			}
			R--;
		}
		for (int y = i.F.F; y <= i.F.S; y++){
			for (auto j: gl[y]){
				if (j.S == 0 && j.F <= i.F.S){
					upd (y, j.F, 1);
				}
			}
		}
		if (get (i.F.F, i.F.S) > 0){
			ans[i.S] = 1;
		}
//		for (int y = i.F.F; y <= i.F.S; y++){
//			for (auto j: gl[y]){
//				if (j.F <= i.F.S){
//					upd (y, j.F, -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: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20