Submission #956139

#	Time	Username	Problem	Language	Result	Execution time	Memory
956139		AlphaMale06	Curtains (NOI23_curtains)	C++17	100 / 100	1055 ms	68696 KiB

curtains

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define int long long

struct query{
	int l, r, ind;
	string ans;
};

const int N = 5e5+3;
pair<int, int> lr[N];
int st[4*N], lz[4*N];
query qs[N];

void push(int v){
	int lc = 2*v+1;
	int rc = 2*v+2;
	st[lc]=max(st[lc], lz[v]);
	st[rc]=max(st[rc], lz[v]);
	lz[lc]=max(lz[lc], lz[v]);
	lz[rc]=max(lz[rc], lz[v]);
	st[v]=min(st[lc], st[rc]);
}

void Update(int v, int l, int r, int L, int R, int val){
	if(l>r || l>R || r<L)return;
	if(l>=L && r<=R){
		st[v]=max(st[v], val);
		lz[v]=max(lz[v], val);
		return;
	}
	push(v);
	int mid = l+r>>1;
	Update(2*v+1, l, mid, L, R, val);
	Update(2*v+2, mid+1, r, L, R, val);
	st[v]=min(st[2*v+1], st[2*v+2]);
}

int Get(int v, int l, int r, int L, int R){
	if(l>r || l>R || r<L)return 1e9;
	if(l>=L && r<=R)return st[v];
	push(v);
	int mid = l+r>>1;
	return min(Get(2*v+1, l, mid, L, R), Get(2*v+2, mid+1, r, L, R));
}

bool cmp1(query A, query B){
	return A.r<B.r;
}
bool cmp2(query A, query B){
	return A.ind < B.ind;
}

void solve(){
	int n, m, q;
	cin >> n >> m >> q;
	for(int i=0; i< m; i++){
		cin >> lr[i].S >> lr[i].F;
	}
	sort(lr, lr+m);
	for(int i=0; i< m; i++){
		swap(lr[i].F, lr[i].S);
	}
	for(int i=0; i< q; i++){
		cin >> qs[i].l >> qs[i].r;
		qs[i].ind=i;
	}
	sort(qs, qs+q, cmp1);
	int p=0;
	for(int i=0; i< q; i++){
		while(p<m && lr[p].S<=qs[i].r){
			Update(0, 1, n, lr[p].F, lr[p].S, lr[p].F);
			p++;
		}
		if(Get(0, 1, n, qs[i].l, qs[i].r)>=qs[i].l)qs[i].ans="YES";
		else qs[i].ans="NO";
	}
	sort(qs, qs+q, cmp2);
	for(int i=0; i< q; i++){
		cout << qs[i].ans << '\n';
	}
}


signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

Compilation message (stderr)

curtains.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:42:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |  int mid = l+r>>1;
      |            ~^~
curtains.cpp: In function 'long long int Get(long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |  int mid = l+r>>1;
      |            ~^~

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