Submission #886248

#	Time	Username	Problem	Language	Result	Execution time	Memory
886248		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 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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20