Submission #170833

#	Time	Username	Problem	Language	Result	Execution time	Memory
170833		bgspartan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3066 ms	51064 KiB

sortbooks

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxN=1000001,INF=9999999999999;
ll w[maxN],ans[maxN];
ll segmMin[maxN*8],segmMax[maxN*8];
ll findMax(ll l,ll r,ll iL,ll iR,ll idx){

    if(l>iR or iL>r){
        return 0;
    }else{
        if(l<=iL and r>=iR){
            return segmMax[idx];
        }else{
            ll ans1,ans2;
            ans1=findMax(l,r,iL,(iL+iR)/2,idx*2);
            ans2=findMax(l,r,(iL+iR)/2+1,iR,idx*2+1);
            return max(ans1,ans2);
        }
    }
}
ll findMin(ll l,ll r,ll iL,ll iR,ll idx){
    if(l>iR or iL>r){
        return INF;
    }else{
        if(l<=iL and r>=iR){
            return segmMin[idx];
        }else{
            ll ans1,ans2;
            ans1=findMin(l,r,iL,(iL+iR)/2,idx*2);
            ans2=findMin(l,r,(iL+iR)/2+1,iR,idx*2+1);
            return min(ans1,ans2);
        }
    }
}
ll query(ll l,ll r,ll k,ll n){
    if(l==r){
      return 1;
    }
    ll intvMax=0,intvMin=0;
    intvMax=findMax(l,r,1,n,1);
    if(w[r-1]==intvMax){
        return query(l,r-1,k,n);
    }
    intvMin=findMin(l,r,1,n,1);
    //cout<<intvMin<<" "<<intvMax<<"\n";
    if(intvMax+intvMin<=k){
        return 1;
    }else{
        if(w[r-1]!=intvMax){
            return 0;
        }else{
            return query(l,r-1,k,n);
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
ll n,m,bp=1;
cin>>n>>m;
for(int i=0;i<n;i++){
    cin>>w[i];
}
while(bp<n){
    bp*=2;
}
for(int i=bp;i<=bp*2-1;i++){
        if(i-bp<n){
        segmMax[i]=w[i-bp];
        segmMin[i]=w[i-bp];
        }else{
         segmMax[i]=0;
         segmMin[i]=INF;
        }
}
for(int i=bp-1;i>=1;i--){
    segmMax[i]=max(segmMax[2*i],segmMax[2*i+1]);
    segmMin[i]=min(segmMin[2*i],segmMin[2*i+1]);

}
for(int i=0;i<m;i++){
    ll l,r,k;
    cin>>l>>r>>k;
    ans[i]=query(l,r,k,bp);
}
for(int i=0;i<m;i++){
    cout<<ans[i]<<"\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