Submission #1256086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256086		mngoc._.	Curtains (NOI23_curtains)	C++20	100 / 100	1202 ms	86056 KiB

curtains

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int , int>
const int N = 5e5 + 5;
const int anhnhoem = 1e18;
vector<pii> queries[N];
vector<int> a[N];
int n  , m  , q;
int st[4 * N] , lazy[4 * N]; 
string res[N];
void down(int idx){
	int k = lazy[idx];
	if(k == 0) return;
	st[2 * idx] = max(st[2 * idx] , k);
	st[2 * idx + 1]  = max(st[2 * idx + 1] , k);
	lazy[2 * idx] = max(lazy[2 * idx] , k);
	lazy[2 * idx + 1] = max(lazy[2 * idx + 1] , k);
	lazy[idx] = 0;
}

void update(int idx , int l , int r , int u , int v , int val){
	if(l > v || r < u) return;
	if(u <= l && r <= v){
		st[idx] = max(st[idx] , val);
		lazy[idx] = max(lazy[idx] , val);
		return;
	}
	down(idx);
	int mid = (l + r) / 2;
	update(2 * idx , l , mid , u , v , val);
	update(2 * idx + 1 , mid + 1 , r , u , v , val);
	st[idx] = min(st[2 * idx] , st[2 * idx + 1]);
}

int get(int idx , int l , int r , int u , int v){
	if(l > v || r < u) return anhnhoem;
	if(u <= l && r <= v){
		return st[idx];
	}
	down(idx);
	int mid = (l + r) / 2;
	return min(get(2 * idx , l , mid , u , v) , get(2 * idx + 1 , mid + 1 , r , u , v));
}


void solve(void){
	cin >> n >> m >> q;
	for(int i = 1 ; i <= m ; i++) {
		int l , r; cin >> l >> r;
		a[r].push_back(l);
	}
	for(int i = 1 ; i <= q ; i ++){
		int l , r; cin >> l >> r;
		queries[r].push_back({l , i});	
	} 
	
	for(int i = 1 ; i <= n ; i++){
		for(auto x : a[i]){
			update(1 , 1 , n , x , i , x);
		}
	    //cout << get(1 , 1 , n , 1 , 4) << endl;
		for(auto x : queries[i]){
			if(get(1 , 1 , n , x.first , i) >= x.first){
				res[x.second] = "YES";
			}
			else{
				res[x.second] = "NO";
			}
		}
		
	}
	for(int i = 1 ; i <= q ; i++) cout << res[i] << endl;
	
	
	
}

signed main(void){
	ios_base :: sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	solve();
	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