Submission #171090

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

sortbooks

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

    if(l>iR or iL>r){
        return {0,0};
    }else{
        if(l<=iL and r>=iR){
            return {segmMax[idx],segmInd[idx]};
        }else{
            ll ans1,ind1,ind2,ans2;
            ans1=findMax(l,r,iL,(iL+iR)/2,idx*2).first;
            ind1=findMax(l,r,iL,(iL+iR)/2,idx*2).second;
            ans2=findMax(l,r,(iL+iR)/2+1,iR,idx*2+1).first;
            ind2=findMax(l,r,(iL+iR)/2+1,iR,idx*2+1).second;
            if(ans1>ans2){
                return {ans1,ind1};
            }else{
                if(ans2>ans1){
                 return {ans2,ind2};
                }else{
                    return {ans1,max(ind1,ind2)};
                }
            }

        }
    }
}

ll query(ll l,ll r,ll k,ll n){
    //cout<<l<<" "<<r<<" "<<k<<" "<<n<<"\n";

        if(l==r){
      return 1;
    }
    ll intvMax=0,intvMaxind=0,intv2Max=0;
    intvMax=findMax(l,r,1,n,1).first;
    intvMaxind=findMax(l,r,1,n,1).second;
    if(w[r-1]==intvMax){
        return query(l,r-1,k,n);
    }
   intv2Max=findMax(intvMaxind+1,r,1,n,1).first;
//cout<<intvMax<<" "<<intvMaxind<<" "<<intv2Max<<"\n";
//system("pause");
  if(intvMax+intv2Max>k){
      return 0;
  }else{
      if(intvMaxind==1)return 1;
    if(intvMax+intv2Max<lastsum){
        return 1;
    }else{
    lastsum=intvMax+intv2Max;
    }
      return query(l,intvMaxind-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];
        segmInd[i]=i-bp+1;
        }else{
         segmMax[i]=0;

        }
}
for(int i=bp-1;i>=1;i--){
        if(segmMax[2*i]>segmMax[2*i+1]){
            segmMax[i]=segmMax[2*i];
            segmInd[i]=segmInd[2*i];
        }else{
               if(segmMax[2*i]<segmMax[2*i+1]){
               segmMax[i]=segmMax[2*i+1];
               segmInd[i]=segmInd[2*i+1];
               }else{
                 segmMax[i]=segmMax[2*i+1];
                  segmInd[i]=max(segmInd[2*i+1],segmInd[2*i]);
               }
        }

}
for(int i=0;i<m;i++){
    ll l,r,k;
    cin>>l>>r>>k;
    lastsum=0;
    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