Submission #1303900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303900		chaitanyamehta	Curtains (NOI23_curtains)	C++20	9 / 100	1597 ms	67468 KiB

curtains

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

#define int long long
vector<vector<int>> st;

struct Segtree{
    int sz = 1;
    vector<vector<int>> s;
    void init(int n){
        while(sz < n)sz*=2;
        s.resize(2*sz);
    }
    void set(int pos , int val){
        pos += sz-1;
        s[pos].push_back(val);
    }
    void build(){
        for(int i = sz - 1; i >= 1; i--){
            sort(s[i * 2].begin() , s[i*2].end());
            sort(s[i*2+1].begin() , s[i*2+1].end());
            vector<int> temp;
            merge(s[i*2].begin() , s[i*2].end() , s[i*2+1].begin() , s[i*2+1].end() , back_inserter(temp));
            s[i].swap(temp);
        }
    }
    int query(int ql , int qr , int l , int r , int cur ,int lim){
        if(l > r || l >qr || r < ql)return -1;
        if(ql <= l && r <= qr){
             
            auto &v = s[cur];
            auto it = upper_bound(v.begin() , v.end() , lim);
            if(it == v.begin())return -1;
            it--;
            return *it;
        }
        int m = (l + r) >>1;
        int L = query(ql , qr , l , m , cur *2 , lim);
        int R = query(ql , qr , m +1 , r , cur*2+1 , lim);
        return max(L , R);
    }

    int query(int l , int r, int lim){
        return query(l , r , 1 , sz -1 , 1 , lim);
    }

};

signed main(){
    int n , m , q;
    cin>>n>>m>>q;

    vector<pair<int , int>> inter(m);
    for(int i = 0 ;i < m ; i++){
        int l , r;cin>>l>>r;
        inter[i] = {l , r};
    }
    
    Segtree st;
    st.init(n);

    for(int i = 0 ; i < m ; i++){
        st.set(inter[i].first , inter[i].second);
    }
    st.build();

    while(q--){
        int l , r;
        cin>>l>>r;

        int cur = l - 1;
        bool ok = true;

        while(cur < r){
            int L = l;
            int R = cur + 1;
            int nxt = st.query(L , R , r);

            if(nxt < R || nxt == -1){ok =false;break;}

            cur = nxt;
        }

        if(ok)cout<<"YES\n";
        else cout<<"NO\n";
    }
}

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