oj.uz

Submission #886243

# Submission time Handle Problem Language Result Execution time Memory
886243 2023-12-11T15:41:02 Z vjudge1 Curtains (NOI23_curtains) C++11
0 / 100
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -