Submission #886197

#	Time	Username	Problem	Language	Result	Execution time	Memory
886197		vjudge1	Curtains (NOI23_curtains)	C++17	29 / 100	1531 ms	84524 KiB

curtains

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

#define ll long long
#define endl "\n"
#define all(aa) aa.begin(), aa.end()

#pragma GCC optimize("O3,unroll-loops")

struct SegmentTree{
    int N;
    vector<int> st, lazy, arr;

    SegmentTree(int N, int val=0): N(N), arr(N, val), st(4*N), lazy(4*N){
        build(1, 0, N-1);
    }

    int build(int n, int s, int e){
        if(s==e) return st[n]=arr[s];
        int mid=(s+e)/2;
        return st[n]=build(n*2, s, mid)+build(n*2+1, mid+1, e);
    }

    void push(int n){
        st[n*2]+=lazy[n]; st[n*2+1]+=lazy[n];
        lazy[n*2]+=lazy[n]; lazy[n*2+1]+=lazy[n];
        lazy[n]=0;
    }

    void update(int n, int s, int e, int l, int r, int val){
        if(s>=l && e<=r){
            lazy[n]+=val;
            st[n]+=val;
            return ;
        }
        push(n);

        int mid=(s+e)/2;
        if(mid>=l) update(n*2, s, mid, l, r, val);
        if(mid<r) update(n*2+1, mid+1, e, l, r, val);
        st[n]=min(st[n*2], st[n*2+1]);
    }

    int query(int n, int s, int e, int l, int r){
        if(s>=l && e<=r) return st[n];
        push(n);

        int mid=(s+e)/2, ans=INT_MAX;
        if(mid>=l) ans=min(ans, query(n*2, s, mid, l, r));
        if(mid<r) ans=min(ans, query(n*2+1, mid+1, e, l, r));
        return ans;
    }

    int query(int l, int r){
        return query(1, 0, N-1, l, r);
    }
    void update(int l, int r, int val){
        return update(1, 0, N-1, l, r, val);
    }
};

const int SQRT=700;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, q;
    cin>>n>>m>>q;

    vector<vector<int>> beg(n), end(n); 
    vector<pair<int, int>> ranges;
    SegmentTree st(n);
    for(int i=0; i<m; i++){
        int a, b;
        cin>>a>>b;
        a--; b--;

        ranges.emplace_back(a, b);
        st.update(a, b, 1);
        beg[a].push_back(i);
        end[b].push_back(i);
    }

    vector<int> pref(n), act(m, 1);
    for(int i=0; i<n; i++)
        pref[i]=(i==0 ? 0:pref[i-1]+beg[i].size()+end[i].size());

    priority_queue<array<int, 4>, vector<array<int, 4>>, greater<array<int, 4>>> mo;
    for(int i=0; i<q; i++){
        int l, r;
        cin>>l>>r;
        l--; r--;

        mo.push({pref[l]/SQRT, r, l, i});
    }

    int cur_l=0, cur_r=n-1;
    vector<bool> ans(q);
    while(mo.size()){
        auto [block, r, l, ind]=mo.top();
        mo.pop();

        for(int i=cur_l; i<l; i++){
            for(auto e:beg[i]) if(act[e]){
                st.update(ranges[e].first, ranges[e].second, -1);
                act[e]=0;
            }
        }
        for(int i=cur_r; i>r; i--){
            for(auto e:end[i]) if(act[e]){
                st.update(ranges[e].first, ranges[e].second, -1);
                act[e]=0;
            }
        }
        for(int i=cur_l; i>=l; i--){
            for(auto e:beg[i]){
                if(!act[e] && ranges[e].second<=r){
                     st.update(ranges[e].first, ranges[e].second, 1);
                     act[e]=1;
                }
            }
        }
        for(int i=cur_r; i<=r; i++){
            for(auto e:end[i]){
                if(!act[e] && ranges[e].first>=l){
                     st.update(ranges[e].first, ranges[e].second, 1);
                     act[e]=1;
                }
            }
        }

        ans[ind]=(st.query(l, r)==0);
        cur_l=l; cur_r=r;
    }

    for(int i=0; i<q; i++) cout<<(ans[i] ? "NO":"YES")<<endl;
}

Compilation message (stderr)

curtains.cpp: In constructor 'SegmentTree::SegmentTree(int, int)':
curtains.cpp:12:27: warning: 'SegmentTree::arr' will be initialized after [-Wreorder]
   12 |     vector<int> st, lazy, arr;
      |                           ^~~
curtains.cpp:12:17: warning:   'std::vector<int> SegmentTree::st' [-Wreorder]
   12 |     vector<int> st, lazy, arr;
      |                 ^~
curtains.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     SegmentTree(int N, int val=0): N(N), arr(N, val), st(4*N), lazy(4*N){
      |     ^~~~~~~~~~~

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