oj.uz

Submission #886172

# Submission time Handle Problem Language Result Execution time Memory
886172 2023-12-11T14:20:31 Z vjudge1 Curtains (NOI23_curtains) C++17
20 / 100
 968 ms 18084 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 7;
const int inf = 1e9 + 7;
struct SEGT{
	pair < int , int > tree[N];
	SEGT(){
		for(int i = 0;i<N;i++){
			tree[i] = {-inf , inf};
		}
	}
	void update(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr){
			tree[ind].first = max(tree[ind].first , ql);
			tree[ind].second = min(tree[ind].second , qr);
			return;
		}
		else if(l > qr or r < ql){
			return;
		}
		else{
			int mid = (l+r)/2;
			update(ind*2,l,mid,ql,qr);
			update(ind*2+1,mid+1,r,ql,qr);
			tree[ind].first = max(tree[ind].first , min(tree[ind*2].first , tree[ind*2+1].first));
			tree[ind].second = min(tree[ind].second , max(tree[ind*2].second , tree[ind*2+1].second));
		}
	}
	bool query(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr){
			return tree[ind].first >= ql and tree[ind].second <= qr;
		}
		else if(l > qr or r < ql){
			return 1;
		}
		else{
			int mid = (l+r)/2;
			return query(ind*2,l,mid,ql,qr) and query(ind*2+1,mid+1,r,ql,qr);
		}
	}
} segt;
void solve(){
	int n,m,q;
	cin >> n >> m >> q;
	for(int i = 0;i<m;i++){
		int x,y;
		cin >> x >> y;
		segt.update(1,1,n,x,y);
	}
	for(int i = 0;i<q;i++){
		int x,y;
		cin >> x >> y;
		cout << (segt.query(1,1,n,x,y) ? "YES" : "NO") << endl;
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Incorrect 4 ms 16072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Incorrect 4 ms 16072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Incorrect 4 ms 16072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 15960 KB Output is correct
2 Correct 4 ms 15960 KB Output is correct
3 Correct 6 ms 15964 KB Output is correct
4 Correct 4 ms 15964 KB Output is correct
5 Correct 9 ms 15964 KB Output is correct
6 Correct 8 ms 15964 KB Output is correct
7 Correct 7 ms 15964 KB Output is correct
8 Correct 643 ms 17936 KB Output is correct
9 Correct 696 ms 17852 KB Output is correct
10 Correct 852 ms 18004 KB Output is correct
11 Correct 706 ms 18084 KB Output is correct
12 Correct 194 ms 16424 KB Output is correct
13 Correct 183 ms 16244 KB Output is correct
14 Correct 161 ms 16364 KB Output is correct
15 Correct 160 ms 16216 KB Output is correct
16 Correct 164 ms 16520 KB Output is correct
17 Correct 156 ms 16156 KB Output is correct
18 Correct 968 ms 17660 KB Output is correct
19 Correct 954 ms 17968 KB Output is correct
20 Correct 819 ms 17464 KB Output is correct
21 Correct 893 ms 17364 KB Output is correct
22 Correct 884 ms 17524 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Incorrect 4 ms 16072 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15964 KB Output is correct
2 Correct 4 ms 15964 KB Output is correct
3 Incorrect 4 ms 16072 KB Output isn't correct
4 Halted 0 ms 0 KB -