oj.uz

Submission #362861

# Submission time Handle Problem Language Result Execution time Memory
362861 2021-02-04T14:11:56 Z shahriarkhan Money (IZhO17_money) C++14
0 / 100
 24 ms 31596 KB 
#include<bits/stdc++.h>
using namespace std ;

const int mx = 2e6 + 45 ;

struct tree
{
    vector<int> t ;

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

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

        if((low==high) && (high==ind))
        {
            ++t[node] ;
            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] = 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 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 24 ms 31596 KB Output is correct
2 Correct 23 ms 31596 KB Output is correct
3 Correct 19 ms 31596 KB Output is correct
4 Correct 19 ms 31596 KB Output is correct
5 Correct 19 ms 31596 KB Output is correct
6 Correct 19 ms 31596 KB Output is correct
7 Correct 19 ms 31596 KB Output is correct
8 Correct 19 ms 31596 KB Output is correct
9 Correct 19 ms 31596 KB Output is correct
10 Incorrect 19 ms 31596 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

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

Subtask #3
0 / 20.0

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

Subtask #4
0 / 55.0

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