oj.uz

Submission #886198

# Submission time Handle Problem Language Result Execution time Memory
886198 2023-12-11T14:44:31 Z vjudge1 Curtains (NOI23_curtains) C++17
29 / 100
 1500 ms 78528 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=1000;

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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 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 344 KB Output is correct
7 Correct 1 ms 344 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 348 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 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 344 KB Output is correct
7 Correct 1 ms 344 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 37 ms 768 KB Output is correct
14 Correct 39 ms 604 KB Output is correct
15 Correct 37 ms 600 KB Output is correct
16 Correct 34 ms 764 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 17 ms 836 KB Output is correct
21 Correct 22 ms 604 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 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 344 KB Output is correct
7 Correct 1 ms 344 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 37 ms 768 KB Output is correct
14 Correct 39 ms 604 KB Output is correct
15 Correct 37 ms 600 KB Output is correct
16 Correct 34 ms 764 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 17 ms 836 KB Output is correct
21 Correct 22 ms 604 KB Output is correct
22 Correct 508 ms 10256 KB Output is correct
23 Execution timed out 1544 ms 9616 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 408 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 197 ms 10924 KB Output is correct
9 Correct 261 ms 11820 KB Output is correct
10 Correct 1031 ms 22648 KB Output is correct
11 Correct 209 ms 10952 KB Output is correct
12 Correct 183 ms 16000 KB Output is correct
13 Correct 175 ms 15944 KB Output is correct
14 Correct 151 ms 16352 KB Output is correct
15 Correct 139 ms 15940 KB Output is correct
16 Correct 155 ms 16268 KB Output is correct
17 Correct 135 ms 15768 KB Output is correct
18 Correct 1448 ms 77100 KB Output is correct
19 Correct 1494 ms 76924 KB Output is correct
20 Correct 1016 ms 78528 KB Output is correct
21 Correct 1010 ms 78204 KB Output is correct
22 Correct 1095 ms 77452 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 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 344 KB Output is correct
7 Correct 1 ms 344 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 37 ms 768 KB Output is correct
14 Correct 39 ms 604 KB Output is correct
15 Correct 37 ms 600 KB Output is correct
16 Correct 34 ms 764 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 17 ms 836 KB Output is correct
21 Correct 22 ms 604 KB Output is correct
22 Execution timed out 1511 ms 6168 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 600 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 344 KB Output is correct
7 Correct 1 ms 344 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 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 37 ms 768 KB Output is correct
14 Correct 39 ms 604 KB Output is correct
15 Correct 37 ms 600 KB Output is correct
16 Correct 34 ms 764 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 3 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 17 ms 836 KB Output is correct
21 Correct 22 ms 604 KB Output is correct
22 Correct 508 ms 10256 KB Output is correct
23 Execution timed out 1544 ms 9616 KB Time limit exceeded
24 Halted 0 ms 0 KB -