Submission #769860

#	Time	Username	Problem	Language	Result	Execution time	Memory
769860		Trunkty	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	13 / 100	1860 ms	100180 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
 
int n,m;
int arr[1000005],bef[1000005];
int maxbef[4000020],maxi[4000020],mini[4000020];

void build(int node, int l, int r){
    if(l==r){
        maxbef[node] = bef[l];
        maxi[node] = arr[l];
        mini[node] = arr[l];
    }
    else{
        int mid = (l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        maxbef[node] = max(maxbef[node*2],maxbef[node*2+1]);
        maxi[node] = max(maxi[node*2],maxi[node*2+1]);
        mini[node] = min(mini[node*2],mini[node*2+1]);
    }
}

int querymaxi(int node, int l, int r, int needl, int needr){
    if(l>needr or r<needl){
        return 0;
    }
    else if(l>=needl and r<=needr){
        return maxi[node];
    }
    else{
        int mid = (l+r)/2;
        return max(querymaxi(node*2,l,mid,needl,needr),querymaxi(node*2+1,mid+1,r,needl,needr));
    }
}

int querymini(int node, int l, int r, int needl, int needr){
    if(l>needr or r<needl){
        return 2e9;
    }
    else if(l>=needl and r<=needr){
        return mini[node];
    }
    else{
        int mid = (l+r)/2;
        return min(querymini(node*2,l,mid,needl,needr),querymini(node*2+1,mid+1,r,needl,needr));
    }
}

int querymaxbef(int node, int l, int r, int needl, int needr){
    if(l>needr or r<needl){
        return -1;
    }
    if(l==r){
        if(maxbef[node]>=needl){
            return l;
        }
        else{
            return -1;
        }
    }
    if(l>=needl and r<=needr){
        if(maxbef[node]<needl){
            return -1;
        }   
        int mid = (l+r)/2;
        if(maxbef[node*2+1]<needl){
            return querymaxbef(node*2,l,mid,needl,needr);
        }
        else{
            return querymaxbef(node*2+1,mid+1,r,needl,needr);
        }
    }
    else{
        int mid = (l+r)/2;
        int x = querymaxbef(node*2+1,mid+1,r,needl,needr);
        if(x!=-1){
            return x;
        }
        else{
            return querymaxbef(node*2,l,mid,needl,needr);
        }
    }
}
 
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> arr[i];
    }
    stack<vector<int>> sk;
    sk.push({2000000000,0});
    for(int i=1;i<=n;i++){
        while(sk.top()[0]<=arr[i]){
            sk.pop();
        }
        bef[i] = sk.top()[1];
        sk.push({arr[i],i});
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        int x = querymaxbef(1,1,n,a,b);
        if(x==-1 or x<a){
            cout << 1 << "\n";
        }
        else{
            if(querymaxi(1,1,n,a,x)+querymini(1,1,n,a,x)<=c){
                cout << 1 << "\n";
            }
            else{
                cout << 0 << "\n";
            }
        }
    }
    return 0;
}

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