Submission #171309

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

sortbooks

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

const ll maxN=1000001,INF=999999999999;
ll w[maxN],ans[maxN];
queue<ll> intervals;
vector<ll> mSortTree[4*maxN+4];
ll sCost[4*maxN+4];
ll tSize=1;

ll mergeCost(ll ind1,ll ind2){
    vector<ll> ::iterator lb;
    ll size1=mSortTree[ind1].size();
    ll size2=mSortTree[ind2].size();
 ll a1,a2,a3,a4;
 a1=mSortTree[ind1][0];
 a2=mSortTree[ind1][size1-1];
 a3=mSortTree[ind2][0];
 a4=mSortTree[ind2][size2-1];
    if(a4<a2){
        return a2+a4;
    }
    if(a2<=a3){
        return 0;
    }
  lb=lower_bound(mSortTree[ind2].begin(),mSortTree[ind2].end(),a2);
  ll indx=0;
  indx=lb-mSortTree[ind2].begin();
  indx--;
  return a2+mSortTree[ind2][indx];
}

void createTree(ll n){

    while(tSize<n){
        tSize*=2;
    }

    for(int i=tSize;i<tSize*2;i++){
        if(i-tSize<n){
            mSortTree[i].push_back(w[i-tSize]);
        }else{
            mSortTree[i].push_back(INF);
        }
        sCost[i]=0;
    }

    for(int i=tSize-1;i>=1;i--){

merge(mSortTree[i*2].begin(),mSortTree[i*2].end(),mSortTree[i*2+1].begin(),mSortTree[i*2+1].end(),back_inserter(mSortTree[i]));

      sCost[i]=mergeCost(i*2,i*2+1);
      //cout<<i<<" "<<sCost[i]<<"\n";
      sCost[i]=max(sCost[i],sCost[i*2]);
      sCost[i]=max(sCost[i],sCost[i*2+1]);
    }

}

void getIntervals(ll l,ll r,ll sl,ll sr,ll idx){
  if(sl>r or sr<l){

  }else{
    if(sl>=l and sr<=r){
        intervals.push(idx);
    }else{
        ll mid=(sl+sr)/2;
        getIntervals(l,r,sl,mid,idx*2);
        getIntervals(l,r,mid+1,sr,idx*2+1);
    }
  }
}

ll query(ll l,ll r,ll n){
    ll qAns=0;
 getIntervals(l,r,1,n,1);
 if(intervals.size()==1){
        qAns=sCost[intervals.front()];
        intervals.pop();
 }else{
    ll prev=intervals.front(),curr=0;
    qAns=sCost[prev];
    intervals.pop();
    while(intervals.empty()==false){
        curr=intervals.front();
        intervals.pop();
        qAns=max(qAns,sCost[curr]);
        qAns=max(qAns,mergeCost(prev,curr));
        prev=curr;
    }
 }
 return qAns;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
ll n,m,l,r,k;
cin>>n>>m;
for(int i=0;i<n;i++){
    cin>>w[i];
}
createTree(n);
for(int i=0;i<m;i++){
    cin>>l>>r>>k;
    if(query(l,r,tSize)>k){
        ans[i]=0;
    }else{
        ans[i]=1;
    }
}
for(int i=0;i<m;i++){
    cout<<ans[i]<<"\n";
}
return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'long long int mergeCost(long long int, long long int)':
sortbooks.cpp:16:5: warning: variable 'a1' set but not used [-Wunused-but-set-variable]
  ll a1,a2,a3,a4;
     ^~

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