oj.uz

Submission #886191

# Submission time Handle Problem Language Result Execution time Memory
886191 2023-12-11T14:33:49 Z vjudge1 Curtains (NOI23_curtains) C++17
0 / 100
 203 ms 7252 KB 
#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.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1368 KB Output is correct
3 Correct 1 ms 1372 KB Output is correct
4 Correct 1 ms 1372 KB Output is correct
5 Correct 1 ms 1372 KB Output is correct
6 Correct 1 ms 1372 KB Output is correct
7 Correct 1 ms 1372 KB Output is correct
8 Correct 60 ms 3136 KB Output is correct
9 Correct 69 ms 3588 KB Output is correct
10 Correct 160 ms 7252 KB Output is correct
11 Correct 60 ms 3500 KB Output is correct
12 Correct 45 ms 2464 KB Output is correct
13 Correct 37 ms 2472 KB Output is correct
14 Correct 33 ms 2388 KB Output is correct
15 Correct 33 ms 2388 KB Output is correct
16 Correct 33 ms 2396 KB Output is correct
17 Correct 33 ms 2396 KB Output is correct
18 Incorrect 203 ms 6992 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

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

Subtask #6
0 / 20.0

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