Submission #1261807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261807		liangjeremy	Curtains (NOI23_curtains)	C++20	100 / 100	774 ms	85980 KiB

curtains

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
using db=double;
using ll=int64_t;
using sll=__int128;
using lb=long double;

const int MAXN=5e5+10;
int lz[MAXN<<2]; int tr[MAXN<<2];
struct queries{
	int idx; int st;
};
void pushdown(int rt){
	if(lz[rt]){
		lz[rt<<1]=max(lz[rt<<1],lz[rt]);
		lz[rt<<1|1]=max(lz[rt<<1|1],lz[rt]);
		tr[rt<<1]=max(tr[rt<<1],lz[rt]);
		tr[rt<<1|1]=max(tr[rt<<1|1],lz[rt]); 
		lz[rt]=0;
	}
}
void update(int l, int r, int rt, int L, int R, int x){
	if(L<=l && r<=R){
		lz[rt]=max(lz[rt],x); tr[rt]=max(tr[rt],x); return;
	}
	int mid=(l+r)>>1; pushdown(rt);
	if(L<=mid)update(l,mid,rt<<1,L,R,x);
	if(R>mid)update(mid+1,r,rt<<1|1,L,R,x); 
	tr[rt]=min(tr[rt<<1],tr[rt<<1|1]); 
}
int query(int l, int r, int rt, int L, int R){
	if(L<=l && r<=R)return tr[rt];
	int mid=(l+r)>>1; pushdown(rt); int ans=1e8;
	if(L<=mid)ans=min(ans,query(l,mid,rt<<1,L,R));
	if(R>mid)ans=min(ans,query(mid+1,r,rt<<1|1,L,R)); 
	return ans; 
}

int32_t main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); srand(time(0));
    int n,m,q; cin>>n>>m>>q; vector<vector<int>>a(n+1);
    for(int i=1; i<=m; i++){
    	int l,r; cin>>l>>r; a[r].push_back(l); 
    }
    vector<vector<queries>>qry(n+1); vector<string>ans(q,"NO");
    for(int i=0; i<q; i++){
    	int l,r; cin>>l>>r; qry[r].push_back({i,l}); 
    }
    for(int i=1; i<=n; i++){
    	for(auto x:a[i])update(1,n,1,x,i,x); 
    	for(auto x:qry[i]){
    		if(query(1,n,1,x.st,i)==x.st)ans[x.idx]="YES"; 
    	}
    }
    for(auto x:ans)cout<<x<<'\n';
}
/*
O what can ail thee, knight-at-arms,
       Alone and palely loitering?
The sedge has withered from the lake,
       And no birds sing.
 
O what can ail thee, knight-at-arms,
       So haggard and so woe-begone?
The squirrel’s granary is full,
       And the harvest’s done.
 
I see a lily on thy brow,
       With anguish moist and fever-dew,
And on thy cheeks a fading rose
       Fast withereth too. 
*/

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