oj.uz

Submission #362832

# Submission time Handle Problem Language Result Execution time Memory
362832 2021-02-04T13:36:18 Z shahriarkhan Money (IZhO17_money) C++14
0 / 100
 16 ms 23788 KB 
#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] , prev = 0 , ans = 0 ;
    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) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        if(!prev)
        {
            T.update(1,1,n,a[i]) , ++ans ;
            prev = a[i] ;
            continue ;
        }
        if(a[i]<prev) prev = a[i] , ++ans ;
        else if(T.find_max(1,1,n,prev+1,a[i])) prev = a[i] , ++ans ;
        else prev = a[i] ;
        T.update(1,1,n,a[i]) ;
    }
    printf("%d\n",ans) ;
    return 0 ;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Incorrect 16 ms 23788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Incorrect 16 ms 23788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Incorrect 16 ms 23788 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB Output is correct
2 Correct 16 ms 23788 KB Output is correct
3 Correct 16 ms 23788 KB Output is correct
4 Incorrect 16 ms 23788 KB Output isn't correct
5 Halted 0 ms 0 KB -