Submission #886207

#	Time	Username	Problem	Language	Result	Execution time	Memory
886207		vjudge1	Curtains (NOI23_curtains)	C++17	100 / 100	665 ms	68648 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 7;
const int inf = 1e9 + 7;
struct SEGT{
	int tree[N];
	SEGT(){
		for(int i = 0;i<N;i++){
			tree[i] = inf;
		}
	}
	void update(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr){
			tree[ind] = min(tree[ind] , 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] = min(tree[ind] , max(tree[ind*2] , tree[ind*2+1]));
		}
	}
	bool query(int ind , int l , int r , int ql , int qr){
		if(l >= ql and r <= qr){
			return tree[ind] <= 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;
	vector < int > ran[n+1];
	vector < pair < int , int > > query[n+1];
	for(int i = 0;i<m;i++){
		int x,y;
		cin >> x >> y;
		ran[x].push_back(y);
	}
	for(int i = 0;i<q;i++){
		int x,y;
		cin >> x >> y;
		query[x].push_back({y,i});
	}
	int ans[q];
	for(int i = n;i>0;i--){
		for(auto itr : ran[i]){
			segt.update(1,1,n,i,itr);
		}
		for(auto itr : query[i]){
			ans[itr.second] = segt.query(1,1,n,i,itr.first);
		}
	}
	for(int i = 0;i<q;i++){
		cout << (ans[i] ? "YES\n" : "NO\n");
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 36 / 36
• Subtask 6: 20 / 20