oj.uz

Submission #890673

# Submission time Handle Problem Language Result Execution time Memory
890673 2023-12-21T18:20:48 Z NotLinux Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 845 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int M = 4e6 + 7;
const long long inf = 1e18 + 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;
        long long 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 , (long long)a.mx + (long long)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:19: warning: 'SegmentTree::Node::ans' will be initialized after [-Wreorder]
   37 |         long long 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 156764 KB Output is correct
2 Incorrect 31 ms 156764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 156764 KB Output is correct
2 Incorrect 31 ms 156764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 845 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 219 ms 170448 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 156764 KB Output is correct
2 Incorrect 31 ms 156764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 156764 KB Output is correct
2 Incorrect 31 ms 156764 KB Output isn't correct
3 Halted 0 ms 0 KB -