This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (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: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]) ;
| ~~~~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |