Submission #886191

#	Time	Username	Problem	Language	Result	Execution time	Memory
886191		vjudge1	Curtains (NOI23_curtains)	C++17	0 / 100	203 ms	7252 KiB

curtains

#include <bits/stdc++.h>
using namespace std;

struct segtr {
	bool tree[1000007];
	static constexpr int n = 500001;
	inline bool query(int l, int r) {
		bool ret = false;
		for(l+=n, r+=n+1; l<r; l>>=1, r>>=1) {
			if(l&1) ret |= tree[l++];
			if(r&1) ret |= tree[--r];
			if(ret) return ret;
		}
		return ret;
	}
	inline void update(int pos, bool val) {
		for(tree[pos+=n]=val; pos>1; pos>>=1) tree[pos>>1] = tree[pos] | tree[pos^1];
	}
	segtr() {}
};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, m, q;
	cin>>n>>m>>q;
	segtr tree;
	vector<pair<int, int>> a(m);
	for(int i=0; i<m; i++) cin>>a[i].first>>a[i].second;
	sort(a.begin(), a.end());
	tree.update(0, true);
	for(int i=0; i<m; i++) {
		if(tree.query(a[i].first-1, a[i].second)) tree.update(a[i].second, true);
	}
	for(int i=0; i<q; i++) {
		int temp, tmp;
		cin>>temp>>tmp;
		if(tree.query(tmp, tmp)) cout<<"YES\n";
		else cout<<"NO\n";
	}
}

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