oj.uz

Submission #886182

# Submission time Handle Problem Language Result Execution time Memory
886182 2023-12-11T14:24:35 Z vjudge1 Curtains (NOI23_curtains) C++17
20 / 100
 988 ms 33880 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
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 7 ms 31580 KB Output is correct
2 Correct 7 ms 31636 KB Output is correct
3 Incorrect 7 ms 31580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31580 KB Output is correct
2 Correct 7 ms 31636 KB Output is correct
3 Incorrect 7 ms 31580 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 31580 KB Output is correct
2 Correct 7 ms 31636 KB Output is correct
3 Correct 7 ms 31580 KB Output is correct
4 Correct 7 ms 31616 KB Output is correct
5 Correct 10 ms 31580 KB Output is correct
6 Correct 10 ms 31632 KB Output is correct
7 Correct 10 ms 31580 KB Output is correct
8 Correct 657 ms 33404 KB Output is correct
9 Correct 654 ms 33616 KB Output is correct
10 Correct 785 ms 33748 KB Output is correct
11 Correct 653 ms 33880 KB Output is correct
12 Correct 193 ms 32004 KB Output is correct
13 Correct 186 ms 32476 KB Output is correct
14 Correct 156 ms 31972 KB Output is correct
15 Correct 157 ms 32056 KB Output is correct
16 Correct 162 ms 32316 KB Output is correct
17 Correct 156 ms 32016 KB Output is correct
18 Correct 949 ms 33568 KB Output is correct
19 Correct 988 ms 33464 KB Output is correct
20 Correct 809 ms 33104 KB Output is correct
21 Correct 814 ms 33240 KB Output is correct
22 Correct 821 ms 33024 KB Output is correct

Subtask #5
0 / 36.0

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

Subtask #6
0 / 20.0

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