// 3250 Bad Hair Day

#include <iostream>
#include <stdlib.h>
using namespace std;

typedef struct cow{
	int height, addr;
} cow;

typedef struct node{
	int value, addr, wall;
} node;

cow input[80001];
int n;
node nodes[80001];

int compare(const void* a, const void* b){
	return (*(cow*)a).height - (*(cow*)b).height;
}

void solve(){
	int sum[80001];
	int index = 0; int i;
	for(i = 0; i < n; i++){
		if(input[i].height <= input[i+1].height){
			nodes[index].addr = i; nodes[index].value = 0; nodes[index].wall = input[i+1].height;
			sum[i] = 0; index++;
		}
	}
	qsort(input, n+1, sizeof(cow), compare);
	for(i = 0; i < n; i++){
		if(sum[input[i].addr] == 0) continue;
		else{
			int s = 0;
			int prev = -1;
			for(int j = 0; j < index; j++){
				if(input[i].addr > nodes[j].addr) continue;
				else{
					if(prev != -1 && nodes[j].addr == prev);
					else{
						nodes[j].value++;
					}
					prev = nodes[j].addr;
					nodes[j].addr = input[i].addr;
					s += nodes[j].value;
					
					if(input[i].height <= nodes[j].wall) break;
				}
			}
			sum[input[i].addr] = s;
		}
	}
	unsigned int result = 0;
	for(i = 0; i < n; i++) result += sum[i];
	printf("%u\n", result);

}

int main(){
	scanf("%d", &n);
	int a;
	for(int i = 0; i < n; i++){
		scanf("%d", &a); input[i].height = a; input[i].addr = i;
	}
	input[n].height = 2000000000; input[n].addr = n;
	solve();

	return 0;
}

find example (WA)... plz..

USACO input : http://train.usaco.org/TESTDATA/NOV06_7.htm

• Re:my program is correct using USACO all input... but WA Why?;; (49) __sunshine 2009-09-24 21:23:51