oj.uz

Submission #886197

# Submission time Handle Problem Language Result Execution time Memory
886197 2023-12-11T14:43:21 Z vjudge1 Curtains (NOI23_curtains) C++17
29 / 100
 1500 ms 84524 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 496 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 496 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 34 ms 604 KB Output is correct
14 Correct 28 ms 600 KB Output is correct
15 Correct 27 ms 604 KB Output is correct
16 Correct 25 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 12 ms 872 KB Output is correct
21 Correct 16 ms 876 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 496 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 34 ms 604 KB Output is correct
14 Correct 28 ms 600 KB Output is correct
15 Correct 27 ms 604 KB Output is correct
16 Correct 25 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 12 ms 872 KB Output is correct
21 Correct 16 ms 876 KB Output is correct
22 Correct 491 ms 12732 KB Output is correct
23 Execution timed out 1527 ms 12244 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 201 ms 13016 KB Output is correct
9 Correct 270 ms 14320 KB Output is correct
10 Correct 961 ms 27008 KB Output is correct
11 Correct 206 ms 12768 KB Output is correct
12 Correct 178 ms 16968 KB Output is correct
13 Correct 184 ms 17224 KB Output is correct
14 Correct 149 ms 17528 KB Output is correct
15 Correct 133 ms 16972 KB Output is correct
16 Correct 133 ms 17476 KB Output is correct
17 Correct 149 ms 17040 KB Output is correct
18 Correct 1396 ms 82744 KB Output is correct
19 Correct 1355 ms 83180 KB Output is correct
20 Correct 978 ms 84524 KB Output is correct
21 Correct 956 ms 83520 KB Output is correct
22 Correct 1008 ms 83288 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 496 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 34 ms 604 KB Output is correct
14 Correct 28 ms 600 KB Output is correct
15 Correct 27 ms 604 KB Output is correct
16 Correct 25 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 12 ms 872 KB Output is correct
21 Correct 16 ms 876 KB Output is correct
22 Execution timed out 1531 ms 7512 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 496 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 34 ms 604 KB Output is correct
14 Correct 28 ms 600 KB Output is correct
15 Correct 27 ms 604 KB Output is correct
16 Correct 25 ms 604 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 2 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 12 ms 872 KB Output is correct
21 Correct 16 ms 876 KB Output is correct
22 Correct 491 ms 12732 KB Output is correct
23 Execution timed out 1527 ms 12244 KB Time limit exceeded
24 Halted 0 ms 0 KB -