Submission #683579

#	Time	Username	Problem	Language	Result	Execution time	Memory
683579		FatihSolak	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	2424 ms	208316 KiB

sortbooks

#include <bits/stdc++.h>
#define N 1000005
#define K 20
using namespace std;
int len[N];
int maxi[N][K];
int val[N][K];
int nxt[N];
int a[N];
struct node{
    int val,maxi;
};
int get(int l,int r){
    if(r < l)
        return 0;
    int ln = r-l+1;
    if(a[maxi[l][len[ln]]] > a[maxi[r - (1<<len[ln]) + 1][len[ln]]])
        return maxi[l][len[ln]];
    else return maxi[r - (1<<len[ln]) + 1][len[ln]];
}
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] = i;
    }
    for(int j = 1;j<K;j++){
        for(int i = 1;i<=n;i++){
            if(i + (1<<j) - 1 <= n){
                maxi[i][j] = maxi[i][j-1];
                if(a[maxi[i][j]] <= a[maxi[i + (1<<(j-1))][j-1]]){
                    maxi[i][j] = maxi[i + (1<<(j-1))][j-1];
                }
            }
        }
    }
    stack<int> st;
    st.push(n+1);
    a[n+1] = 1e9 + 5;
    a[0] = -1e9;
    for(int i =n;i>=1;i--){
        while(a[st.top()] < a[i])
            st.pop();
        assert(st.size());
        nxt[i] = st.top();
        st.push(i);
    }
    for(int j = 1;j<K;j++){
        for(int i =1;i<=n;i++){
            if(i + (1<<j) - 1 <= n){
                val[i][j] = max(val[i][j-1],val[i + (1<<(j-1))][j-1]);
                val[i][j] = max(val[i][j],a[maxi[i][j-1]] + a[get(i + (1<<(j-1)),min(nxt[maxi[i][j-1]]-1,i + (1<<j) - 1))]);
            }  
        }
    }

    for(int i = 1;i<=m;i++){
        int l,r,k;
        cin >> l >> r >> k;
        int now = 0;
        int tmp = l;
        for(int j = K-1;j>=0;j--){
            if(tmp + (1<<j) - 1 <= r){
                now = max(now,val[tmp][j]);
                if(tmp != l)
                    now = max(now,a[get(l,tmp-1)] + a[get(tmp,min(nxt[get(l,tmp-1)]-1,tmp + (1<<j) - 1))]);
                tmp += (1<<j);
            }
        }
        cout << (now <= k) << '\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: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 23 / 23