Define N[i] to be the first cow to the right of cow i which is taller than cow i. It's quite obvious that calculating N[i] for all i is equivalent to solving the problem.
An easy observation is that if h[i]>h[j], n[i]>j, then n[i]>=n[j]
since if n[i] Code (by Brian Dean):
#include <stdio.h>
#define MAX_N 100000
int N, h[MAX_N], n[MAX_N];
unsigned int solve(void) {
unsigned int T = 0;
int i, c;
for (i=N-1; i>=0; i--) {
c = 0; n[i] = i+1;
while (n[i] < N && h[n[i]] < h[i]) {
c += n[n[i]] - n[i];
n[i] = n[n[i]];
}
T += c;
}
return T;
}
int main(void) {
FILE *fp;
int i;
fp = fopen ("badhair.in", "r");
fscanf (fp, "%d", &N);
for (i=0; i<N; i++) fscanf (fp, "%d", &h[i]);
fclose (fp);
fp = fopen ("badhair.out", "w");
fprintf (fp, "%u\n", solve());
fclose (fp);
return 0;
}