Submission #1133081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133081		chinhhoang	Curtains (NOI23_curtains)	C++20	100 / 100	742 ms	113512 KiB

curtains

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6;
int tree[N*4+666];
void update(int id,int l,int r,int u,int v){
    if(u<=l&&r<=v){
        tree[id]=min(tree[id],v);
        return;
    }
    if(v<l||r<u)return;
    int mid=(l+r)/2;
    update(id*2,l,mid,u,v);
    update(id*2+1,mid+1,r,u,v);
    tree[id]=min(tree[id],max(tree[id*2],tree[id*2+1]));
}
bool get(int id,int l,int r,int u,int v){
    if(v<l||r<u)return 1;
    if(u<=l&&r<=v)return tree[id]<=v;
    int mid=(l+r)/2;
    return get(id*2,l,mid,u,v)&&get(id*2+1,mid+1,r,u,v);
}
vector<int>vv[N];
vector<pair<int,int>>a[N];
int ans[N];
signed main() {
	cin.tie(0)->sync_with_stdio(0);
	//freopen("tasks.inp","r",stdin);
	//freopen("tasks.out","w",stdout);
	int n,m,q;
	cin>>n>>m>>q;
	for(int i=1;i<=4*N;i++)tree[i]=3489342783472;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        vv[u].push_back(v);
    }
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        a[l].push_back({r,i});
    }
    for(int i=1;i<=n;i++)sort(vv[i].begin(),vv[i].end()),sort(a[i].begin(),a[i].end());
    for(int i=n;i>=1;i--){
        for(auto v:vv[i])update(1,1,n,i,v);
       for(auto d:a[i])ans[d.second]=get(1,1,n,i,d.first);
    }
    for(int i=1;i<=q;i++)cout<<(ans[i]?"YES":"NO")<<'\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