Submission #886254

#TimeUsernameProblemLanguageResultExecution timeMemory
886254vjudge1Curtains (NOI23_curtains)C++11
20 / 100
1033 ms18196 KiB
#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++){
			if(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]-1, 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;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...