Submission #171545

#	Time	Username	Problem	Language	Result	Execution time	Memory
171545		juggernaut	Money (IZhO17_money)	C++14	100 / 100	826 ms	26744 KiB

money

//Just try and the idea will come!
#include<bits/stdc++.h>
using namespace std;
int mx,n,i,a[1000001],ans,tree[4000004];
void update(int v,int l,int r,int pos,int val){
    if(l==pos&&r==pos){
            tree[v]=val;
            return;
      }
      int mid=(l+r)>>1;
      if(pos<=mid)update((v*2),l,mid,pos,val);
      else update((v*2)+1,mid+1,r,pos,val);
      tree[v]=min(tree[(v*2)],tree[(v*2)+1]);
}
int get(int v,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return tree[v];
    if(r<ql||qr<l)return 1000001;
    int mid=(l+r)>>1;
    return min(get((v*2),l,mid,ql,qr),get((v*2)+1,mid+1,r,ql,qr));
}
main(){
    for(i=0;i<4000004;i++)tree[i]=1000001;
    scanf("%d",&n);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    i=0;
    while(i<n){
        mx=get(1,1,1000001,a[i]+1,1000001);
        update(1,1,1000001,a[i],a[i]);
        while(i+1<n&&a[i]<=a[i+1]&&a[i+1]<=mx)i++,update(1,1,1000001,a[i],a[i]);;
        i++;
        ans++;
    }
    printf("%d",ans);
}

Compilation message (stderr)

money.cpp:21:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
money.cpp: In function 'int main()':
money.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
money.cpp:24:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=0;i<n;i++)scanf("%d",&a[i]);
                     ~~~~~^~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55