Submission #952769

#	Time	Username	Problem	Language	Result	Execution time	Memory
952769		idiotcomputer	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	64 / 100	3058 ms	262148 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define f first 
#define s second

const int mxN = 1e6;
int n;
int vals[mxN];

int smax[4*mxN+1];
int ans[4*mxN+1];
vector<int> all[4*mxN+1];

void build(int l = 0, int r = n-1, int idx = 0){
    if (l == r){
        smax[idx] = vals[l];
        ans[idx] = 0;
        all[idx].pb(vals[l]);
        return;
    }
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
    smax[idx] = max(smax[2*idx+1],smax[2*idx+2]);
    ans[idx] = max(ans[2*idx+1],ans[2*idx+2]);
    int cidx = lower_bound(all[2*idx+2].begin(),all[2*idx+2].end(),smax[2*idx+1]) - all[2*idx+2].begin();
    if (cidx > 0) ans[idx] = max(ans[idx], smax[2*idx+1] + all[2*idx+2][cidx-1]);
    cidx = 0;
    for (int i = 0; i < m-l+1; i++){
        while (cidx < r-m && all[2*idx+2][cidx] < all[2*idx+1][i]){
            all[idx].pb(all[2*idx+2][cidx]);
            cidx++;
        }
        all[idx].pb(all[2*idx+1][i]);
    }
    while (cidx < r-m){
        all[idx].pb(all[2*idx+2][cidx]);
        cidx++;
    }
    return;
}

pii query(int tl, int tr, int cmax = 0, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl) return {0,0};
    if (l >= tl && r <= tr){
        int cidx = lower_bound(all[idx].begin(),all[idx].end(),cmax) - all[idx].begin();
        if (cidx > 0) return {max(ans[idx], all[idx][cidx-1] + cmax),smax[idx]};
        return {ans[idx],smax[idx]};
    }
    int m = (l+r)/2;
    pii v1 = query(tl,tr,cmax,l,m,2*idx+1);
    pii v2 = query(tl,tr,max(cmax,v1.s),m+1,r,2*idx+2);
    return {max(v1.f,v2.f), max(cmax,max(v1.s,v2.s))};
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int m;
    cin >> n >> m;
    
    for (int i =0; i < n; i++) cin >> vals[i];
    
    build();
    int l,r,k;
    for (int i = 0; i < m; i++){
        cin >> l >> r >> k;
        l -= 1;
        r -= 1;
        pii res = query(l,r);
        if (res.f <= k) cout << "1\n";
        else cout << "0\n";
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23