Submission #364736

#TimeUsernameProblemLanguageResultExecution timeMemory
364736nicolaalexandraMoney (IZhO17_money)C++14
0 / 100
1 ms364 KiB
#include <bits/stdc++.h> #define DIM 1000010 using namespace std; int aib[DIM],dp[DIM],v[DIM]; int n,i,maxi,val; void update (int p, int val){ for (;p<=maxi;p+=(p&-p)) aib[p] += val; } int query (int p){ int sol = 0; for (;p;p-=(p&-p)) sol += aib[p]; return sol; } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n; for (i=1;i<=n;i++){ cin>>v[i]; maxi = max (maxi,v[i]); } i = 1; while (v[i] > v[i-1]){ dp[i] = 1; i++; } int st = i; for (;i<=n;i++){ if (v[i] < v[i-1]){ st = i; dp[i] = dp[i-1] + 1; } else { do{ val = query (v[i]) - query (v[st]-1); if (val){ update (v[st],1); st++; } } while (val); dp[i] = dp[st-1] + 1; } } cout<<dp[n]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...