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>
#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>0;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]);
}
int sol = 0;
for (i=1;i<=n;i++){
int j = i;
while (j < n && v[j+1] >= v[j] && query(v[j+1]-1) - query(v[i]) == 0)
j++;
sol++;
/// acum fac update pt ca termin cu secv asta
for (int poz=i;poz<=j;poz++)
update (v[poz],1);
i = j;
}
cout<<sol;
return 0;
}
# | 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... |