2304번: 창고 다각형 – 스택

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

1. 가장 높은 기둥을 찾으세요.

2. 열에서 시작하여 각각 왼쪽과 오른쪽 끝에 스택을 씁니다.

– 높이가 상단보다 낮으면 을 누릅니다. 높이가 더 높으면 상단이 더 높아질 때까지 누르십시오.

3. 스태킹 정보를 사용하여 면적을 계산합니다.

#define _SILENCE_ALL_CXX20_DEPRECATION_WARNINGS
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N;
vector<pii> pillar;
int mxIdx;
int mx{ 0 };

bool compare(pii a, pii b)
{
    return (a.second < b.second)
        || (a.second == b.second && a.first > b.first);
}

int ans{ 0 };

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> N;
    for (int i{ 1 }; i <= N; i++)
    {
        int L, H; cin >> L >> H;

        pillar.push_back({ L, H });
    }
    sort(pillar.begin(), pillar.end());

    for (int i{ 0 }; i < pillar.size(); i++)
    {
        auto (L, H) = pillar(i);
        if (mx < H)
        {
            mx = H;
            mxIdx = i;
        }
    }

    stack<pii> left;
    left.push(pillar(mxIdx));
    for (int i{ mxIdx - 1 }; i >= 0; i--)
    {
        auto (L, H) = pillar(i);
        while (H > left.top().second) left.pop();

        left.push(pillar(i));
    }

    stack<pii> right;
    right.push({ pillar(mxIdx).first + 1, pillar(mxIdx).second });
    for (int i{ mxIdx + 1 }; i < pillar.size(); i++)
    {
        auto (L, H) = pillar(i);
        while (H > right.top().second) right.pop();

        right.push({ ++L, H });
    }

    int ans{ pillar(mxIdx).second };
    int L, H;

    L = left.top().first, H = left.top().second ;
    left.pop();
    while (true)
    {
        if (left.empty()) break;

        ans += H * (left.top().first - L);
        L = left.top().first, H = left.top().second;
        left.pop();
    }
    L = right.top().first, H = right.top().second;
    right.pop();
    while (true)
    {
        if (right.empty()) break;

        ans += H * (L - right.top().first);
        L = right.top().first, H = right.top().second;
        right.pop();
    }

    cout << ans;
}