백준 2493 : 탑

Algorithm

백준 2493 : 탑

쿠케캬캬 2021. 11. 14. 01:52

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

2493번: 탑

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1

www.acmicpc.net

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

#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 };
	}
}