oj.uz

Submission #683560

# Submission time Handle Problem Language Result Execution time Memory
683560 2023-01-18T17:56:34 Z FatihSolak Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 158596 KB 
#include <bits/stdc++.h>
#define N 1000005
#define K 20
using namespace std;
int len[N];
int maxi[N][K];
int nxt[N];
int a[N];
int ans[N];
struct node{
    int val = 0,maxi = -1;
};
int gett(int l,int r){
    if(r < l)
        return -1e9;
    int ln = r-l+1;
    return max(maxi[l][len[ln]],maxi[r - (1<<len[ln]) + 1][len[ln]]);
}
struct SegTree{
    vector<node> t;
    int n;
    SegTree(int sz){
        n = sz;
        t.assign(4*n,{0,0});
        build(1,1,n);
    }
    node merge(node x,node y){
        node ret = x;
        ret.val = max(ret.val,y.val);
        if(a[y.maxi] > a[x.maxi])
            ret.maxi = y.maxi;
        return ret;
    }
    void build(int v,int tl,int tr){
        if(tl == tr){
            t[v].maxi = tl;
            return;
        }
        int tm = (tl + tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
        t[v] = merge(t[v*2],t[v*2+1]);
        for(int i = tm+1;i<=tr;i++){
            if(a[i] < a[t[v*2].maxi]){
                t[v].val = max(t[v].val,a[t[v*2].maxi] + a[i]);
            }
        }
    }
    node get(int v,int tl,int tr,int l,int r){
        if(tr < l || r < tl){
            return {0,0};
        }
        if(l <= tl && tr <= r){
            return t[v];
        }
        int tm = (tl + tr)/2;
        node x = get(v*2,tl,tm,l,r);
        node y = get(v*2+1,tm+1,tr,l,r);
        if(x.maxi > 0)
            x.val = max(x.val,a[x.maxi] + gett(max(l,tm+1),min({nxt[x.maxi]-1,r,tr})));
        return merge(x,y);
    }
    node get(int l,int r){
        return get(1,1,n,l,r);
    }
};
void solve(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i<=n;i++){
        len[i] = len[i-1];
        if((1<<(len[i]+1)) < i)
            len[i]++;
        cin >> a[i];
        maxi[i][0] = a[i];
    }
    for(int j = 1;j<K;j++){
        for(int i = 1;i<=n;i++){
            if(i + (1<<j) - 1 <= n)
                maxi[i][j] = max(maxi[i][j-1],maxi[i + (1<<(j-1))][j-1]);
        }
    }
    stack<int> st;
    st.push(n+1);
    a[n+1] = 1e9 + 5;
    for(int i =n;i>=1;i--){
        while(a[st.top()] <= a[i])
            st.pop();
        nxt[i] = st.top();
        st.push(i);
    }
    SegTree t(n);
    for(int i = 1;i<=m;i++){
        int l,r,k;
        cin >> l >> r >> k;
        ans[i] = t.get(l,r).val <= k;
    }
    for(int i = 1;i<=m;i++){
        cout << ans[i] << '\n';
    }
}
    
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2924 ms 127596 KB Output is correct
2 Execution timed out 3034 ms 158596 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Incorrect 1 ms 340 KB Output isn't correct
11 Halted 0 ms 0 KB -