Submission #169910

#	Time	Username	Problem	Language	Result	Execution time	Memory
169910		juggernaut	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	2355 ms	142112 KiB

sortbooks

//Just try and the idea will come!
#include<bits/stdc++.h>
#define int long long int
using namespace std;
int n,m,pos[1000001],a[1000001],i,tree[4000001],l[1000001],r[1000001],k[1000001],ans[1000001];
vector<vector<int>>g(1000001);
void update(int v,int l,int r,int ind,int val){
    if(l==r){tree[v]=val;return;}
    int m=(l+r)>>1;
    if(ind<=m)update(v*2,l,m,ind,val);
    else update(v*2+1,m+1,r,ind,val);
    tree[v]=max(tree[v*2],tree[v*2+1]);
}
int get(int v,int l,int r,int ql,int qr){
    if(qr<l||r<ql)return 0;
    if(ql<=l&&r<=qr)return tree[v];
    int mid=(l+r)>>1;
    return max(get(v*2,l,mid,ql,qr),get(v*2+1,mid+1,r,ql,qr));
}
main(){
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        pos[i]=i-1;
        while(pos[i]&&a[pos[i]]<=a[i])pos[i]=pos[pos[i]];
    }
    for(i=1;i<=m;i++){
        scanf("%lld%lld%lld",&l[i],&r[i],&k[i]);
        g[r[i]].push_back(i);
    }
    for(i=1;i<=n;i++){
        if(pos[i])update(1,1,n,pos[i],a[i]+a[pos[i]]);
        for(int to:g[i])ans[to]=(get(1,1,n,l[to],r[to])<=k[to]?1:0);
    }
    for(i=1;i<=m;i++)printf("%lld\n",ans[i]);
}

Compilation message (stderr)

sortbooks.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~
sortbooks.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&a[i]);
         ~~~~~^~~~~~~~~~~~~~
sortbooks.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld%lld",&l[i],&r[i],&k[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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