Submission #886204

#	Time	Username	Problem	Language	Result	Execution time	Memory
886204		vjudge1	Curtains (NOI23_curtains)	C++17	60 / 100	1545 ms	79436 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 > query[n+1] , ran[n+1];
	for(int i = 0;i<m;i++){
		int x,y;
		cin >> x >> y;
		ran[x].push_back(y);
	}
	map < pair < int , int > , int > mpa;
	vector < pair < int , int > > v;
	for(int i = 0;i<q;i++){
		int x,y;
		cin >> x >> y;
		v.push_back({x,y});
		query[x].push_back(y);
	}
	for(int i = n;i>0;i--){
		for(auto itr : ran[i]){
			segt.update(1,1,n,i,itr);
		}
		for(auto itr : query[i]){
			mpa[{i,itr}] = segt.query(1,1,n,i,itr);
		}
	}
	for(auto itr : v){
		cout << (mpa[itr] ? "YES" : "NO") << endl;
	}
}
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: 0 / 20
• Subtask 5: 36 / 36
• Subtask 6: 0 / 20