oj.uz

Submission #886199

# Submission time Handle Problem Language Result Execution time Memory
886199 2023-12-11T14:45:21 Z vjudge1 Curtains (NOI23_curtains) C++17
9 / 100
 1500 ms 77556 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=450;

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 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 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 348 KB Output is correct
2 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 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 19 ms 604 KB Output is correct
14 Correct 19 ms 600 KB Output is correct
15 Correct 19 ms 600 KB Output is correct
16 Correct 17 ms 788 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 856 KB Output is correct
20 Correct 9 ms 836 KB Output is correct
21 Correct 13 ms 604 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 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 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 19 ms 604 KB Output is correct
14 Correct 19 ms 600 KB Output is correct
15 Correct 19 ms 600 KB Output is correct
16 Correct 17 ms 788 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 856 KB Output is correct
20 Correct 9 ms 836 KB Output is correct
21 Correct 13 ms 604 KB Output is correct
22 Correct 475 ms 10172 KB Output is correct
23 Execution timed out 1515 ms 10212 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 788 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 220 ms 10532 KB Output is correct
9 Correct 267 ms 12096 KB Output is correct
10 Correct 993 ms 22652 KB Output is correct
11 Correct 222 ms 11056 KB Output is correct
12 Correct 182 ms 15940 KB Output is correct
13 Correct 196 ms 15792 KB Output is correct
14 Correct 129 ms 16208 KB Output is correct
15 Correct 137 ms 15940 KB Output is correct
16 Correct 170 ms 16128 KB Output is correct
17 Correct 165 ms 15780 KB Output is correct
18 Execution timed out 1536 ms 77556 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 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 19 ms 604 KB Output is correct
14 Correct 19 ms 600 KB Output is correct
15 Correct 19 ms 600 KB Output is correct
16 Correct 17 ms 788 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 856 KB Output is correct
20 Correct 9 ms 836 KB Output is correct
21 Correct 13 ms 604 KB Output is correct
22 Execution timed out 1561 ms 6220 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 0 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 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 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 19 ms 604 KB Output is correct
14 Correct 19 ms 600 KB Output is correct
15 Correct 19 ms 600 KB Output is correct
16 Correct 17 ms 788 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 856 KB Output is correct
20 Correct 9 ms 836 KB Output is correct
21 Correct 13 ms 604 KB Output is correct
22 Correct 475 ms 10172 KB Output is correct
23 Execution timed out 1515 ms 10212 KB Time limit exceeded
24 Halted 0 ms 0 KB -