Submission #362828

#	Time	Username	Problem	Language	Result	Execution time	Memory
362828		shahriarkhan	Money (IZhO17_money)	C++14	0 / 100	19 ms	23788 KiB

money

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

const int mx = 1e6 + 5 ;

struct tree
{
    vector<int> t ;

    tree(int n)
    {
        t = vector<int> (4*n + 4 , 0) ;
    }

    void update(int node , int low , int high , int ind)
    {
        if(high<ind || low>ind) return ;

        if(low==high && high==ind)
        {
            t[node] = 1 ;
            return ;
        }

        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        update(left,low,mid,ind) ;
        update(right,mid+1,high,ind) ;
        t[node] = max(t[left],t[right]) ;
    }

    int find_max(int node , int low , int high , int l , int r)
    {
        if(l>r) return 0 ;
        if(l>high || r<low) return 0 ;
        if(l<=low && high<=r) return t[node] ;
        int mid = (low+high)>>1 , left = node<<1 , right = left|1 ;
        return max(find_max(left,low,mid,l,r),find_max(right,mid+1,high,l,r)) ;
    }
};

int main()
{
    int n ;
    scanf("%d",&n) ;
    int a[n+1] , b[n+1] , cur = 1 , ans = 1 ;
    vector<int> ind[mx] ;
    for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) , b[i] = a[i] ;
    sort(b+1,b+n+1) ;
    for(int i = n ; i >= 1 ; --i)
    {
        ind[b[i]].push_back(i) ;
    }
    for(int i = 1 ; i <= n ; ++i)
    {
        int old = a[i] ;
        a[i] = ind[a[i]].back() ;
        ind[old].pop_back() ;
    }
    tree T(n+5) ;
    T.update(1,1,n,a[1]) ;
    while(cur<n)
    {
        while(((cur+1)<=n) && (a[cur]>a[cur+1]))
        {
            T.update(1,1,n,a[cur+1]) ;
            ++cur , ++ans ;
        }
        while(((cur+1)<=n) && (a[cur]<=a[cur+1]))
        {
            T.update(1,1,n,a[cur+1]) ;
            if(T.find_max(1,1,n,a[cur]+1,a[cur+1]-1))
            {
                ++cur , ++ans ;
                break ;
            }
            ++cur ;
        }
    }
    printf("%d\n",ans) ;
    return 0 ;
}

Compilation message (stderr)

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

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