Submission #886175

#	Time	Username	Problem	Language	Result	Execution time	Memory
886175		vjudge1	Curtains (NOI23_curtains)	C++17	20 / 100	1071 ms	25868 KiB

curtains

#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
• Subtask 2: 0 / 6
• Subtask 3: 0 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 36
• Subtask 6: 0 / 20