Submission #886243

#	Time	Username	Problem	Language	Result	Execution time	Memory
886243		vjudge1	Curtains (NOI23_curtains)	C++11	0 / 100	1 ms	348 KiB

curtains

#include <bits/stdc++.h>
#define pb push_back
#define all(aa) aa.begin(), aa.end()
using namespace std;

struct ST{
	int n;
	vector<int> ok, t;

	ST(vector<int> a) : ok(a){
		n = a.size();
		t.resize(4*n);
		build(1, 0, n-1);
	}

	void build(int u, int tl, int tr){
		if(tl == tr){
			t[u] = ok[tl];
			return;
		}
		int tm = (tl + tr)/2;
		build(u*2, tl, tm);
		build(u*2+1, tm+1, tr);
		t[u] = t[u*2] | t[u*2+1];
	}

	void upd(int u, int tl, int tr, int pos){
		if(tl == tr){
			t[u] = 1;
			return;
		}
		int tm = (tl + tr)/2;
		upd(u*2, tl, tm, pos);
		upd(u*2+1, tm+1, tr, pos);
		t[u] = t[u*2] | t[u*2+1];
	}

	void upd(int pos){
		upd(1, 0, n-1, pos);
	}

	int query(int u, int tl, int tr, int ql, int qr){
		if(ql <= tl && tr <= qr)
			return t[u];

		int tm = (tl + tr)/2;
		int ans = 0;
		if(ql <= tm)
			ans |= query(u*2, tl, tm, ql, qr);
		if(tm < qr)
			ans |= query(u*2+1, tm+1, tr, ql, qr);
		return ans; 
	}

	int query(int l, int r){
		return query(1, 0, n-1, l, r);
	}
};

int main(){
	int n, m, q;
	cin >> n >> m >> q;
	vector<set<int>> go(n);
	vector<int> ok(n);
	vector<int> mn(n);
	iota(all(mn), 0);

	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		--a, --b;
		go[b].insert(a);
		mn[b] = min(a, mn[b]);
		if(a == 0) ok[b] = 1;
	}

	ST st(ok);

	for(int i = 0; i < n; i++){
		if(mn[i] == i) continue;
		if(st.query(mn[i]-1, i)){
			ok[i] = 1;
			st.upd(i);
		}
	}
	for(int i = 0; i < q; i++){
		int a, b;
		cin >> a >> b;
		--a, --b;
		cout << (ok[b] ? "YES" : "NO") << endl;
	}

}

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