백준 2493 : 탑

https://www.acmicpc.net/problem/2493

2493번: 탑

 

​

왼쪽에 현재 탑보다 이미 큰 탑이 있고, 그 큰 탑보다 왼쪽에 있는 탑들이 작다면, 그 작은 탑들로는 어차피 갈 일이 없습니다.

#include <iostream>
int n, a, top = -1;
std::pair<int, int> stk[500000];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n && scanf("%d", &a); i++) {
		while (top != -1 && stk[top].first < a) top--;
		if (top == -1) printf("0 ");
		else printf("%d ", stk[top].second);
		stk[++top] = { a, i };
	}
}