[정올 1141] 불쾌한 날

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=421&sca=99&sfl=wr_hit&stx=1141 

JUNGOL

#include <stdio.h>

struct cow 
{
	int idx;
	int height;
};

cow st1[80010], st2[180010];
int sp1, sp2, N;
unsigned long long sum;

void push_back(cow C)
{
	st1[sp1++] = C;
}
void push_back2(cow C)
{
	st2[sp2++] = C;
}
cow pop()
{
	cow empty;
	empty.height = empty.idx = -1;
	if (sp1 != 0)	return st1[--sp1];
	else			return empty;
}
cow pop2()
{
	cow empty;
	empty.height = empty.idx = -1;
	if (sp2 != 0)	return st2[--sp2];
	else			return empty;
}

void Input()
{
	scanf("%d", &N);
	cow C;
	//역순으로 스택에 넣는다
	for (int i = N-1; i >= 0; i--)
	{
		C.idx = i;
		scanf("%d", &C.height);
		st1[i] = C;
	}
	sp1 = N;
}
void Check()
{
	cow cowRight, cowLeft; //역순으로 스택에 넣었으니, 오른쪽이 먼저 넣은 것

	while (sp1)
	{
		cowRight = pop();
		cowLeft = pop();
		if (cowLeft.height == -1)
		{//전부 다 계산해서 넣는다.
			cow keepCow;
			while (sp2)
			{
				keepCow = pop2();
				sum += keepCow.idx;
			}
		}
		else if (cowLeft.height >= cowRight.height)
		{
			//sum += cowRight.idx - cowLeft.idx;
			//이전에 저장된 애들 중에서도 있는 지 확인
			cow keepCow;
			while (sp2)
			{
				keepCow = pop2();
				if (cowLeft.height >= keepCow.height)
				{//keep 된 놈보다 크면, 계산
					sum += keepCow.idx - cowLeft.idx - 1;
				}
				else
				{//아니면 다시 넣음
					push_back2(keepCow);
					break;
				}
			}
			push_back(cowLeft);
		}
		else
		{
			push_back2(cowRight);
			push_back(cowLeft);
		}
	}
}

int main(void)
{
	Input();
	Check();
	printf("%lld\n", sum);

	return 0;
}