Submission #1209159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209159		lalig777	Curtains (NOI23_curtains)	C++20	100 / 100	943 ms	53488 KiB

curtains

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
#define int long long
using namespace std;

vector<pair<int,int> >seg;

void push(int p){
	seg[p*2].first=min(seg[p].second, seg[p*2].first);
	seg[p*2+1].first=min(seg[p].second, seg[p*2+1].first);
	seg[p*2].second=min(seg[p].second, seg[p*2].second);
	seg[p*2+1].second=min(seg[p].second, seg[p*2+1].second);
	seg[p].second=1e9;
}

int find_max(int l, int r, int a, int b, int p){
	if (l==a && r==b) return seg[p].first;
	else if (l>b || r<a) return -1;
	int m=(l+r)/2;
	push(p);
	int max1=find_max(l, m, a, min(m, b), p*2);
	int max2=find_max(m+1, r, max(a, m+1), b, p*2+1);
	seg[p].first=max(seg[p*2].first, seg[p*2+1].first);
	return max(max1, max2);
}

void prop(int l, int r, int a, int b, int p, int x){
	if (l==a && r==b){
		seg[p].first=min(x, seg[p].first);
		seg[p].second=min(x, seg[p].second);
		return;
	}else if (l>b || r<a) return;
	push(p);
	int m=(l+r)/2;
	prop(l, m, a, min(m, b), p*2, x);
	prop(m+1, r, max(m+1, a), b, p*2+1, x);
	seg[p].first=max(seg[p*2].first, seg[p*2+1].first);
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m, q;
	cin>>n>>m>>q;
	priority_queue<pair<int,int> >cortines;
	for (int i=0; i<m; i++){
		int l, r; cin>>l>>r; l--; r--;
		cortines.push(make_pair(l, r));
	}
	vector<pair<pair<int,int>, int> >query(q);
	for (int i=0; i<q; i++){
		cin>>query[i].first.first>>query[i].first.second;
		query[i].first.first--; query[i].first.second--;
		query[i].second=i;
	}sort(query.begin(), query.end());
	vector<bool>ans(q, false);
	seg.assign(4*n, make_pair(1e9, 1e9));

	for (int i=q-1; i>=0; i--){
		int s=query[i].first.first, e=query[i].first.second;
		while (!cortines.empty()){
			if (cortines.top().first<s) break;
			else{
				int l=cortines.top().first;
				int r=cortines.top().second;
				prop(0, n-1, l, r, 1, r);
				cortines.pop();
			}
		}
		if (find_max(0, n-1, s, e, 1)<=e) ans[query[i].second]=true;
	}
	for (int i=0; i<q; i++){
		if (ans[i]==true) cout<<"YES\n";
		else cout<<"NO\n";
	}

	return 0;
}

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