Submission #1212183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212183		vtnoo	Curtains (NOI23_curtains)	C++20	100 / 100	1146 ms	87296 KiB

curtains

/*
 * puedo ordenar las consultas, hacer todo offline, si tengo una query[s, e]
 * l[i]==s, SE PUEDEN SUPERPONER
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>

#define pb push_back
#define snd second
#define fst first
#define forn(i,n) for(int i=0;i<n;++i)
#define forsn(i,s,n) for(int i=s; i<n; ++i)
#define all(x) x.begin(), x.end()
#define imp(x) for(auto __:x)cout<<__<<" "; cout<<endl;
#define sz(c) int((c).size())
#define mset(a,v) memset((a), (v), sizeof(a));

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;

const int N=500005, inf=1e9;
int st[N*4], lazy[N*4];

void push(int node, int s, int e){
	if(lazy[node]==inf)return;
	st[node]=min(st[node], lazy[node]);
	if(s<e){
		lazy[node*2]=min(lazy[node*2],lazy[node]);
		lazy[node*2+1]=min(lazy[node*2+1],lazy[node]);
	}
	lazy[node]=inf;
}

void update(int node, int s, int e, int v, const int& l, const int& r){
	push(node,s,e);
	if(e<l||s>r){
		return;
	}else if(l<=s&&e<=r){
		lazy[node]=v;
		push(node,s,e);
		return;
	}
	int m=(s+e)/2;
	update(node*2, s, m, v, l, r);
	update(node*2+1, m+1, e, v, l, r);
	st[node]=max(st[node*2], st[node*2+1]);
}

int query(int node, int s, int e, const int& l, const int& r){
	push(node,s,e);
	if(e<l||s>r){
		return 0;
	}else if(l<=s&&e<=r){
		return st[node];
	}
	int m=(s+e)/2;
	return max(query(node*2, s, m, l, r), query(node*2+1, m+1, e, l, r));
}

int main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,q;cin>>n>>m>>q;
	forn(i,N*4)st[i]=inf, lazy[i]=inf;
	vi l(m), r(m);
	vector<string> w(q);
	vector<vi> range(n); 
	vector<vector<ii>> que(n);
	forn(i,m){
		cin>>l[i]>>r[i];
		l[i]--;r[i]--;
		range[l[i]].push_back(r[i]);
	}
	forn(i,q){
		int s,e;cin>>s>>e;
		s--;e--;
		que[s].push_back({e,i});
	}
	for(int i=n-1; i>=0; i--){//i==l
		for(auto rr:range[i]){
			update(1, 0, n-1, rr, i, rr);
		}
		for(auto [rr, idx]:que[i]){
			w[idx]=(query(1, 0, n-1, i, rr)==rr?"YES":"NO");
		}
	}
	forn(i,q)cout<<w[i]<<endl;
}	

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