Submission #690817

#	Time	Username	Problem	Language	Result	Execution time	Memory
690817		White	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	1470 ms	107928 KiB

sortbooks

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

long long seg[4000005],red[1000005],ans[1000005];
vector<pair<pair<long long,long long>,long long>>q[1000005];

void update(long long l,long long r, long long now, long long pos,long long sum){
    if(r<pos || l>pos)return ;
    //cout<<sum<<" -0-0-"<<endl;
    if(l==r){
        seg[now]=max(seg[now],sum);
        return ;
    }
    long long mid=(l+r)/2;
    if(mid>=pos)update(l,mid,now*2+1,pos,sum);
    else update(mid+1,r,now*2+2,pos,sum);
    seg[now]=max(seg[now*2+1],seg[now*2+2]);
}

long long find_ans(long long l,long long r,long long L,long long R,long long now){
    if(L>R)return 0;
    //cout<<seg[now]<<" "<<now<<" P"<<l<<" "<<r<<endl;
    if(l==L && r==R)return seg[now];
    long long mid=(l+r)/2;
    //cout<<l<<" "<<r<<endl;
    return max(find_ans(l,mid,L,min(R,mid),now*2+1),find_ans(mid+1,r,max(L,mid+1),R,now*2+2));
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++){cin>>red[i];}
    for(int i=0;i<m;i++){
        long long l,r,k;
        cin>>l>>r>>k;
        l--;r--;
        q[l].push_back({{r,k},i});
    }

    stack<int>s;
    for(int i=n-1;i>=0;i--){
        while(s.empty()!=true && red[i]>=red[s.top()]){
            if(red[i]!=red[s.top()]){
                    //cout<<i<<" ()()"<<red[s.top()]+red[i]<<endl;
                update(0,n-1,0,s.top(),red[s.top()]+red[i]);
            }
            s.pop();
        }
        s.push(i);
        for(int j=0;j<q[i].size();j++){
            long long ha=find_ans(0,n-1,i,q[i][j].first.first,0);
            //cout<<ha<<" - "<<q[i][j].first.first<<" "<<q[i][j].first.second<<endl;
            if(ha<=q[i][j].first.second){
                ans[q[i][j].second]=1;
            }else{
                ans[q[i][j].second]=0;
            }
        }
    }

    for(int i=0;i<m;i++){
        cout<<ans[i]<<endl;
    }

    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for(int j=0;j<q[i].size();j++){
      |                     ~^~~~~~~~~~~~

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