oj.uz

Submission #886175

# Submission time Handle Problem Language Result Execution time Memory
886175 2023-12-11T14:20:59 Z vjudge1 Curtains (NOI23_curtains) C++17
20 / 100
 1071 ms 25868 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 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 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Incorrect 7 ms 23912 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 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Incorrect 7 ms 23912 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 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Incorrect 7 ms 23912 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 7 ms 23900 KB Output is correct
2 Correct 7 ms 23900 KB Output is correct
3 Correct 9 ms 23896 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 9 ms 23900 KB Output is correct
6 Correct 8 ms 23896 KB Output is correct
7 Correct 9 ms 23900 KB Output is correct
8 Correct 701 ms 25632 KB Output is correct
9 Correct 661 ms 25844 KB Output is correct
10 Correct 845 ms 25868 KB Output is correct
11 Correct 722 ms 25684 KB Output is correct
12 Correct 191 ms 24148 KB Output is correct
13 Correct 186 ms 24180 KB Output is correct
14 Correct 168 ms 24140 KB Output is correct
15 Correct 177 ms 24148 KB Output is correct
16 Correct 187 ms 24224 KB Output is correct
17 Correct 181 ms 24148 KB Output is correct
18 Correct 1020 ms 25492 KB Output is correct
19 Correct 1071 ms 25660 KB Output is correct
20 Correct 841 ms 25236 KB Output is correct
21 Correct 813 ms 25172 KB Output is correct
22 Correct 870 ms 25300 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Incorrect 7 ms 23912 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 23896 KB Output is correct
2 Correct 6 ms 23900 KB Output is correct
3 Incorrect 7 ms 23912 KB Output isn't correct
4 Halted 0 ms 0 KB -