Submission #1099120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099120		0pt1mus23	Curtains (NOI23_curtains)	C++14	100 / 100	847 ms	92452 KiB

curtains

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ins insert      
#define pb push_back

#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
#define _ << " " <<
mt19937 rng(time(0));

const int mod = 998244353,
        sze = 5e5 +23,
        inf = INT_MAX,    
        Lg = 31;
int T[sze*4];
int L[sze*4];

void upd(int l,int r,int v,int node=1,int lx=0,int rx=sze){
    if(lx>r || rx<l){
        return;
    }
    // cout<<node<<endl;
    if(lx>=l && rx<=r){
        // cout<<lx<<" "<<rx<<" "<<v<<endl;
        T[node]=min(T[node],v);
        L[node]=min(L[node],v);
        return; 
    }
    int mid = (lx+rx)/2;
    upd(l,r,v,node*2,lx,mid);
    upd(l,r,v,node*2 +1,mid+1,rx);
    T[node]=min(max(T[node*2],T[node*2 +1]),L[node]);
}
int qry(int l,int r,int node=1,int lx=0,int rx=sze){
    if(lx>r || rx<l){
        return inf*2;
    }
    if(l<=lx && rx<=r){
        return T[node] ;
    }
    int mid = (lx+rx)/2;
    int left = qry(l,r,node*2,lx,mid);
    int right = qry(l,r,node*2 +1,mid+1,rx);
    if(left>inf){
        return min(L[node],right);
    }
    if(right>inf){
        return min(L[node],left);
    }
    return min(max(left,right),L[node]);
}


void _0x0(){
    for(int i=0;i<sze*4;i++){
        T[i]=inf;
        L[i]=inf;
    }
    int n,m,q;
    cin>>n>>m>>q;
    vector<pair<int,int>> event[n+10];
    vector<int> ans(q);
    for(int i=0;i<m;i++){
        int l,r;cin>>l>>r;
        event[l].pb({-1,r});
    }
    for(int i=0;i<q;i++){
        int l,r;cin>>l>>r;
        event[l].pb({i,r});
    }
    for(int i = n;i>=1;i--){
        sort(all(event[i]));
        for(auto [k,v]:event[i]){
            if(k==-1){
                upd(i,v,v);
            }
            else{
                int x = qry(i,v);
                // cout<<i _ ":" _ v _ ".." _ x _ "::"<<endl;
                ans[k]=(x<=v);
            }
        }
    }


    for(auto v:ans) cout<<(v?"YES":"NO")<<endl;
    // upd(2,5,3);
    // cout<<qry(2,5)<<endl;
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = 1;

    // cin>>tt;
    while(tt--){
        _0x0();
    }
 
    return 0;
}

Compilation message (stderr)

curtains.cpp: In function 'void _0x0()':
curtains.cpp:76:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |         for(auto [k,v]:event[i]){
      |                  ^

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