Submission #955885

#	Time	Username	Problem	Language	Result	Execution time	Memory
955885		MilosMilutinovic	Curtains (NOI23_curtains)	C++14	100 / 100	967 ms	82744 KiB

curtains

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m,q;
int mini[4000005],tag[4000005],ans[500005];
vector<int> seg[500005];
vector<pii> qry[500005];

void push(int id){
	chkmax(mini[id<<1],tag[id]);
	chkmax(mini[id<<1|1],tag[id]);
	chkmax(tag[id<<1],tag[id]);
	chkmax(tag[id<<1|1],tag[id]);
	tag[id]=0;
}

void change(int id,int l,int r,int ql,int qr,int v){
	if(ql<=l&&r<=qr){
		chkmax(tag[id],v);
		chkmax(mini[id],v);
		push(id);
		return;
	}
	push(id);
	int mid=(l+r)/2;
	if(qr<=mid) change(id<<1,l,mid,ql,qr,v);
	else if(ql>mid) change(id<<1|1,mid+1,r,ql,qr,v);
	else change(id<<1,l,mid,ql,qr,v),change(id<<1|1,mid+1,r,ql,qr,v);
	mini[id]=min(mini[id<<1],mini[id<<1|1]);
}

int query(int id,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return mini[id];
	push(id);
	int mid=(l+r)/2;
	int ret=0;
	if(qr<=mid) ret=query(id<<1,l,mid,ql,qr);
	else if(ql>mid) ret=query(id<<1|1,mid+1,r,ql,qr);
	else ret=min(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
	mini[id]=min(mini[id<<1],mini[id<<1|1]);
	return ret;
}

int main(){
	n=readint(); m=readint(); q=readint();
	int l,r;
	for(int i=1;i<=m;i++){
		l=readint(); r=readint();
		seg[r].pb(l);
	}
	for(int i=1;i<=q;i++){
		l=readint(); r=readint();
		qry[r].pb(mp(l,i));
	}
	for(int i=1;i<=n;i++){
		for(auto p:seg[i]) change(1,1,n,p,i,p);
		for(auto p:qry[i]) ans[p.se]=(query(1,1,n,p.fi,i)>=p.fi?1:0);
	}
	for(int i=1;i<=q;i++){
		if(ans[i]==0) printf("NO\n");
		else printf("YES\n");
	}
	printf("\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