CODE FESTIVAL 2014 予選B D - 登山家

問題

code-festival-2014-qualb.contest.atcoder.jp

解法

stack でがんばります。

まず, この問題では「右側に見える範囲」及び「左側に見える範囲」を別々に求められれば良いことがわかります。ということで, 右側に見える範囲を求めてみましょう。それがわかれば左側に見える範囲は配列 h を reverse させるだけで出来ます。

山の高さが非増加の間はどんどん山の高さ, 座標を stack に入れ込んでいきます。増加してしまったら, その座標を i として, stack の中で h[i] より小さいものは stack から削除していって, 右側に見える範囲を確定します。

const int MAXN = 100010;
int N;
int h[MAXN], ans[MAXN];

void calc() {
    stack<pii> S;
    int cur = 0;
    while (cur < N) {
        S.push(pii(h[cur], cur));
        int i = cur+1;
        while (S.top().first >= h[i] && i < N) {
            S.push(pii(h[i], i));
            i++;
        }
        while (!S.empty() && S.top().first < h[i]) {
            auto p = S.top();
            ans[p.second] += i-1-p.second;
            S.pop();
        }
        cur = i;
    }
    while (!S.empty()) {
        auto p = S.top();
        ans[p.second] += N-1-p.second;
        S.pop();
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> h[i];
    }
    calc();
    reverse(h, h+N);
    reverse(ans, ans+N);
    calc();
    reverse(ans, ans+N);
    for (int i = 0; i < N; i++) cout << ans[i] << endl;
    return 0;
}