oj.uz

Submission #890680

# Submission time Handle Problem Language Result Execution time Memory
890680 2023-12-21T18:25:03 Z NotLinux Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int M = 3e6 + 7;
const int inf = 2e9 + 7;
// bool debug_mode = 0;
struct MergeSortTree{
    vector < int > tree[M];
    void build(vector < int > &v , int ind=1 , int l=1 , int r=N){
        for(int i = l-1;i<r;i++){
            tree[ind].push_back(v[i]);
        }
        sort(tree[ind].begin() , tree[ind].end());
        if(l != r){
            int mid = (l+r) >> 1;
            build(v , ind*2 , l , mid);
            build(v , ind*2+1 , mid+1 , r);
        }
    }
    inline int query(int ind , int val){
        auto it = lower_bound(tree[ind].begin() , tree[ind].end() , val);
        int res = -1;
        if(it != tree[ind].begin()){
            res = *(--it);
        }
        // if(debug_mode){
        //     cout << "v : ";for(auto itr : tree[ind])cout << itr << " ";cout << endl;
        //     cout << "val : " << val << endl;
        //     cout << "res : " << res << endl;
        // }
        return res;
    }
} mst;
struct SegmentTree{
    struct Node{
        int mx , indx;
        int ans;
        Node():mx(0) , ans(-inf) , indx(0){}
    } tree[M];
    Node merge(Node &a , Node &b){
        Node c;
        c.mx = max(a.mx , b.mx);
        int tmp = mst.query(b.indx , a.mx);
        if(tmp != -1){
            c.ans = max({a.ans , b.ans , (int)a.mx + (int)tmp});
        }
        else {
            c.ans = max(a.ans , b.ans);
        }
        return c;
    }
    void build(vector < int > &v , int ind=1 , int l=1 , int r=N){
        for(int i = l-1;i<r;i++){
            tree[ind].mx = max(tree[ind].mx , v[i]);
        }
        if(l != r){
            int mid = (l+r) >> 1;
            build(v , ind*2 , l , mid);
            build(v , ind*2+1 , mid+1 , r);
            tree[ind] = merge(tree[ind*2] , tree[ind*2+1]);
        }
        tree[ind].indx = ind;
        // cout << l << " " << r << " => " << tree[ind].mx << " " << tree[ind].ans << endl;
    }
    vector < Node > vec;
    void dfs(int ql , int qr , int ind=1 , int l=1 , int r=N){
        if(l >= ql and r <= qr){
            // cout << l << " " << r << " : " << tree[ind].mx << " " << tree[ind].ans << endl;
            vec.push_back(tree[ind]);
        }
        else if(l > qr or r < ql){
            return;
        }
        else{
            int mid = (l+r) >> 1;
            dfs(ql , qr , ind*2 , l , mid);
            dfs(ql , qr , ind*2+1 , mid+1 , r);
        }
    }
    int query(int l , int r){
        Node ret;
        // debug_mode = 1;
        for(auto itr : vec){
            ret = merge(ret , itr);
            // cout << ret.mx << " " << ret.ans << endl;
        }
        // debug_mode = 0;
        vec.clear();
        // cout << "query : " << ret.ans << endl;
        return ret.ans;
    }
} segt;
void solve(){
    int n,m;
    cin >> n >> m;
    vector < int > arr(n);
    for(int i = 0;i<n;i++){
        cin >> arr[i];
    }
    mst.build(arr,1,1,arr.size());
    segt.build(arr,1,1,arr.size());
    // cout << "---" << endl;
    for(int qt = 0;qt<m;qt++){
        int l,r,k;
        cin >> l >> r >> k;
        segt.dfs(l,r,1,1,arr.size());
        cout << (segt.query(l,r) <= k) << '\n';
        // cout << "---" << endl;
    }
}
signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int testcase = 1;//cin >> testcase;
    while(testcase--)solve();
}

Compilation message

sortbooks.cpp: In constructor 'SegmentTree::Node::Node()':
sortbooks.cpp:37:13: warning: 'SegmentTree::Node::ans' will be initialized after [-Wreorder]
   37 |         int ans;
      |             ^~~
sortbooks.cpp:36:18: warning:   'int SegmentTree::Node::indx' [-Wreorder]
   36 |         int mx , indx;
      |                  ^~~~
sortbooks.cpp:38:9: warning:   when initialized here [-Wreorder]
   38 |         Node():mx(0) , ans(-inf) , indx(0){}
      |         ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 106072 KB Output is correct
2 Correct 22 ms 106072 KB Output is correct
3 Correct 23 ms 106072 KB Output is correct
4 Correct 22 ms 106116 KB Output is correct
5 Correct 25 ms 106076 KB Output is correct
6 Correct 22 ms 106028 KB Output is correct
7 Correct 23 ms 106428 KB Output is correct
8 Correct 22 ms 106100 KB Output is correct
9 Correct 22 ms 106076 KB Output is correct
10 Correct 23 ms 105940 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 106072 KB Output is correct
2 Correct 22 ms 106072 KB Output is correct
3 Correct 23 ms 106072 KB Output is correct
4 Correct 22 ms 106116 KB Output is correct
5 Correct 25 ms 106076 KB Output is correct
6 Correct 22 ms 106028 KB Output is correct
7 Correct 23 ms 106428 KB Output is correct
8 Correct 22 ms 106100 KB Output is correct
9 Correct 22 ms 106076 KB Output is correct
10 Correct 23 ms 105940 KB Output is correct
11 Correct 24 ms 106076 KB Output is correct
12 Correct 27 ms 106588 KB Output is correct
13 Correct 27 ms 106588 KB Output is correct
14 Correct 28 ms 106588 KB Output is correct
15 Correct 29 ms 106584 KB Output is correct
16 Correct 27 ms 106588 KB Output is correct
17 Correct 25 ms 106332 KB Output is correct
18 Correct 27 ms 106792 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3041 ms 262144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 119640 KB Output is correct
2 Correct 217 ms 119812 KB Output is correct
3 Correct 157 ms 119764 KB Output is correct
4 Correct 194 ms 119764 KB Output is correct
5 Correct 165 ms 119764 KB Output is correct
6 Correct 140 ms 119632 KB Output is correct
7 Correct 135 ms 119600 KB Output is correct
8 Correct 143 ms 119592 KB Output is correct
9 Correct 54 ms 106324 KB Output is correct
10 Correct 135 ms 119548 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 106072 KB Output is correct
2 Correct 22 ms 106072 KB Output is correct
3 Correct 23 ms 106072 KB Output is correct
4 Correct 22 ms 106116 KB Output is correct
5 Correct 25 ms 106076 KB Output is correct
6 Correct 22 ms 106028 KB Output is correct
7 Correct 23 ms 106428 KB Output is correct
8 Correct 22 ms 106100 KB Output is correct
9 Correct 22 ms 106076 KB Output is correct
10 Correct 23 ms 105940 KB Output is correct
11 Correct 24 ms 106076 KB Output is correct
12 Correct 27 ms 106588 KB Output is correct
13 Correct 27 ms 106588 KB Output is correct
14 Correct 28 ms 106588 KB Output is correct
15 Correct 29 ms 106584 KB Output is correct
16 Correct 27 ms 106588 KB Output is correct
17 Correct 25 ms 106332 KB Output is correct
18 Correct 27 ms 106792 KB Output is correct
19 Correct 547 ms 134404 KB Output is correct
20 Correct 501 ms 134364 KB Output is correct
21 Correct 417 ms 134184 KB Output is correct
22 Correct 414 ms 134352 KB Output is correct
23 Correct 414 ms 134204 KB Output is correct
24 Correct 314 ms 134396 KB Output is correct
25 Correct 298 ms 134252 KB Output is correct
26 Correct 351 ms 134512 KB Output is correct
27 Correct 351 ms 134304 KB Output is correct
28 Correct 374 ms 134496 KB Output is correct
29 Correct 410 ms 134256 KB Output is correct
30 Correct 388 ms 134256 KB Output is correct
31 Correct 369 ms 134352 KB Output is correct
32 Correct 400 ms 134352 KB Output is correct
33 Correct 377 ms 134352 KB Output is correct
34 Correct 279 ms 134352 KB Output is correct
35 Correct 279 ms 134204 KB Output is correct
36 Correct 279 ms 134352 KB Output is correct
37 Correct 286 ms 134216 KB Output is correct
38 Correct 280 ms 134612 KB Output is correct
39 Correct 361 ms 134352 KB Output is correct
40 Correct 223 ms 122328 KB Output is correct
41 Correct 304 ms 134348 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 106072 KB Output is correct
2 Correct 22 ms 106072 KB Output is correct
3 Correct 23 ms 106072 KB Output is correct
4 Correct 22 ms 106116 KB Output is correct
5 Correct 25 ms 106076 KB Output is correct
6 Correct 22 ms 106028 KB Output is correct
7 Correct 23 ms 106428 KB Output is correct
8 Correct 22 ms 106100 KB Output is correct
9 Correct 22 ms 106076 KB Output is correct
10 Correct 23 ms 105940 KB Output is correct
11 Correct 24 ms 106076 KB Output is correct
12 Correct 27 ms 106588 KB Output is correct
13 Correct 27 ms 106588 KB Output is correct
14 Correct 28 ms 106588 KB Output is correct
15 Correct 29 ms 106584 KB Output is correct
16 Correct 27 ms 106588 KB Output is correct
17 Correct 25 ms 106332 KB Output is correct
18 Correct 27 ms 106792 KB Output is correct
19 Execution timed out 3041 ms 262144 KB Time limit exceeded
20 Halted 0 ms 0 KB -