oj.uz

Submission #886248

# Submission time Handle Problem Language Result Execution time Memory
886248 2023-12-11T15:52:39 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 BIT{
	int n;
	vector<int> cnt, fen;
	BIT(vector<int> a) : cnt(a){
		n = a.size();
		fen.resize(n);
		for(int i = 0; i < n; i++){
			fen[i] += cnt[i];
			upd(i);
		}
	}

	void upd(int pos){
		for(int j = pos; j < n; j = j|(j+1)){
			fen[j] += 1;
		}
	}

	int find(int pos){
		int ret = 0;
		for(int j = pos; j >= 0; j = (j & (j + 1)) - 1)
			ret += fen[j];
		return ret;
	}

	int find(int l, int r){
		return find(r) - find(l - 1);
	}
};

int main(){
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> cnt(n);
	vector<int> ok(n);
	vector<int> mn(n, n+1);
	for(int i = 0; i < m; i++){
		int a, b;
		cin >> a >> b;
		--a, --b;
		mn[b] = min(mn[b], a);
		if(a == 0) cnt[b] = 1;
	}

 	BIT fen(cnt);

	for(int i = 0; i < n; i++){
		if(fen.find(mn[i], i) > 0){
			ok[i] = 1;
			fen.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 Incorrect 1 ms 348 KB Output isn't correct
3 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 -