Submission #362853

#	Time	Username	Problem	Language	Result	Execution time	Memory
362853		shahriarkhan	Money (IZhO17_money)	C++14	100 / 100	210 ms	15084 KiB

money

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

const int mx = 1e6 + 45 ;

int T[mx] ;

void add(int pos)
{
    for(; pos < mx ; pos += (pos & -pos)) ++T[pos] ;
}

int get(int pos)
{
    int res = 0 ;
    for(; pos > 0 ; pos -= (pos & -pos)) res += T[pos] ;
    return res ;
}

int find_max(int l , int r)
{
    if(l>r) return 0 ;
    return get(r) - get(l-1) ;
}

int main()
{
    int n ;
    scanf("%d",&n) ;
    int a[n+1] , ans = 0 ;
    for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        int ed = i ;
        while(((ed+1)<=n) && ((a[ed+1]>=a[ed]) && (!find_max(a[i]+1,a[ed+1]-1)))) ++ed ;
        ++ans ;
        for(int j = i ; j <= ed ; ++j) add(a[j]) ;
        i = ed ;
    }
    printf("%d\n",ans) ;
    return 0 ;
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |     scanf("%d",&n) ;
      |     ~~~~~^~~~~~~~~
money.cpp:31:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) ;
      |                                   ~~~~~^~~~~~~~~~~~

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