Submission #952765

#	Time	Username	Problem	Language	Result	Execution time	Memory
952765		idiotcomputer	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	0 / 100	3022 ms	59900 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

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

int smin[4*mxN+1];
int smax[4*mxN+1];
int miss[4*mxN+1];

void build(int l = 0, int r = n-1, int idx = 0){
    if (l == r){
        smin[idx] = vals[l];
        smax[idx] = vals[l];
        miss[idx] = -1;
        return;
    }
    int m = (l+r)/2;
    build(l,m,2*idx+1);
    build(m+1,r,2*idx+2);
    smin[idx] = min(smin[2*idx+1],smin[2*idx+2]);
    smax[idx] = max(smax[2*idx+1],smax[2*idx+2]);
    if (miss[2*idx+2] != -1){
        miss[idx] = max(smax[2*idx+1],miss[2*idx+2]);
    } else {
        if (smax[2*idx+1] <= smin[2*idx+2]){
            miss[idx] = miss[2*idx+1];
        } else {
            miss[idx] = smax[2*idx+1];
        }
    }
    return;
}

int qmin(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
    if (tl > tr) return 2e9;
    if (l > tr || r < tl){
        return 2e9;
    } 
    if (l >= tl && r <= tr){
        return smin[idx];
    }
    int m = (l+r)/2;
    return min(qmin(tl,tr,l,m,2*idx+1), qmin(tl,tr,m+1,r,2*idx+2));
}

int qmax(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
    if (tl > tr) return 0;
    if (l > tr || r < tl){
        return 0;
    } 
    if (l >= tl && r <= tr){
        return smax[idx];
    }
    int m = (l+r)/2;
    return max(qmax(tl,tr,l,m,2*idx+1), qmax(tl,tr,m+1,r,2*idx+2));
}

int query(int tl, int tr, int l = 0, int r = n-1, int idx = 0){
    if (l > tr || r < tl){
        return -1;
    } 
    if (l >= tl && r <= tr){
        return miss[idx];
    }
    int m = (l+r)/2;
    int v1 = query(tl,tr,l,m,2*idx+1);
    int v2 = query(tl,tr,m+1,r,2*idx+2);
    int cmax = qmax(max(tl,l),min(tr,m),l,m,2*idx+1);
    int cmin = qmin(max(tl,m+1),min(tr,r),m+1,r,2*idx+2);
    if (v2 != -1) return max(cmax,v2);
    if (cmax <= cmin) return v1;
    return cmax;
}


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;
        int v = query(l,r);
        int cmin = qmin(l,r);
        if (v == -1 || cmin + v <= k) cout << "1\n";
        else cout << "0\n";
    }
    return 0;
}

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