oj.uz

Submission #362842

# Submission time Handle Problem Language Result Execution time Memory
362842 2021-02-04T13:53:57 Z shahriarkhan Money (IZhO17_money) C++14
0 / 100
 12 ms 15980 KB 
#include<bits/stdc++.h>
using namespace std ;

const int mx = 1e6 + 45 ;

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] , ans = 0 ;
    for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) ;
    tree T(mx) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        int ed = i ;
        while(((ed+1)<=n) && (a[ed+1]>=a[ed]) && (!T.find_max(1,1,n,a[i]+1,a[ed+1]-1))) ++ed ;
        ++ans ;
        for(int j = i ; j <= ed ; ++j) T.update(1,1,n,a[j]) ;
        i = ed ;
    }
    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:46:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   46 |     for(int i = 1 ; i <= n ; ++i) scanf("%d",&a[i]) ;
      |                                   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15980 KB Output is correct
2 Correct 10 ms 15980 KB Output is correct
3 Correct 10 ms 15980 KB Output is correct
4 Correct 10 ms 15980 KB Output is correct
5 Correct 10 ms 15980 KB Output is correct
6 Correct 10 ms 15980 KB Output is correct
7 Correct 10 ms 15980 KB Output is correct
8 Correct 10 ms 15980 KB Output is correct
9 Correct 10 ms 15980 KB Output is correct
10 Incorrect 11 ms 15980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15980 KB Output is correct
2 Correct 10 ms 15980 KB Output is correct
3 Correct 10 ms 15980 KB Output is correct
4 Correct 10 ms 15980 KB Output is correct
5 Correct 10 ms 15980 KB Output is correct
6 Correct 10 ms 15980 KB Output is correct
7 Correct 10 ms 15980 KB Output is correct
8 Correct 10 ms 15980 KB Output is correct
9 Correct 10 ms 15980 KB Output is correct
10 Incorrect 11 ms 15980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15980 KB Output is correct
2 Correct 10 ms 15980 KB Output is correct
3 Correct 10 ms 15980 KB Output is correct
4 Correct 10 ms 15980 KB Output is correct
5 Correct 10 ms 15980 KB Output is correct
6 Correct 10 ms 15980 KB Output is correct
7 Correct 10 ms 15980 KB Output is correct
8 Correct 10 ms 15980 KB Output is correct
9 Correct 10 ms 15980 KB Output is correct
10 Incorrect 11 ms 15980 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15980 KB Output is correct
2 Correct 10 ms 15980 KB Output is correct
3 Correct 10 ms 15980 KB Output is correct
4 Correct 10 ms 15980 KB Output is correct
5 Correct 10 ms 15980 KB Output is correct
6 Correct 10 ms 15980 KB Output is correct
7 Correct 10 ms 15980 KB Output is correct
8 Correct 10 ms 15980 KB Output is correct
9 Correct 10 ms 15980 KB Output is correct
10 Incorrect 11 ms 15980 KB Output isn't correct
11 Halted 0 ms 0 KB -