Submission #362842

#TimeUsernameProblemLanguageResultExecution timeMemory
362842shahriarkhanMoney (IZhO17_money)C++14
0 / 100
12 ms15980 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...