結果

問題 No.3017 交互浴
コンテスト
ユーザー れいん
提出日時 2026-07-13 16:59:49
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 132 ms / 2,000 ms
+ 676µs
コード長 2,629 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,025 ms
コンパイル使用メモリ 338,084 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2026-07-13 17:00:05
合計ジャッジ時間 12,008 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

struct onsen
{
    int l, r, c;
    bool operator<(const onsen &other) const
    {
        if (r != other.r)
            return r < other.r;
        if (l != other.l)
            return l < other.l;
        return c < other.c;
    }
    bool operator==(const onsen &other) const
    {
        return l == other.l && r == other.r && c == other.c;
    }
};

int main()
{
    int N;
    cin >> N;
    vector<int> H(N);
    for (int i = 0; i < N; i++)
    {
        cin >> H[i];
    }
    set<onsen> st;
    int ans = 0;
    for (int i = 0; i < N; i++)
    {
        auto it = st.lower_bound({0, H[i], 0});
        if (it == st.end())
        {
            while (!st.empty())
            {
                onsen o = *st.begin();
                if (o.c == 0)
                {
                    ans -= o.r - o.l + 1;
                }
                st.erase(st.begin());
            }
            if (i % 2 == 0)
            {
                ans += H[i];
            }
            st.insert({1, H[i], i % 2});
        }
        else
        {
            if (it->c != i % 2)
            {
                onsen o = *it;

                while (1)
                {
                    onsen now = *st.begin();
                    st.erase(st.begin());
                    if (now.c == 0)
                    {
                        ans -= now.r - now.l + 1;
                    }
                    if (now == o)
                    {
                        break;
                    }
                }
                st.insert({1, H[i], i % 2});
                if (i % 2 == 0)
                {
                    ans += H[i];
                }
                if (H[i] + 1 <= o.r)
                {
                    st.insert({H[i] + 1, o.r, o.c});
                    if (o.c == 0)
                    {
                        ans += o.r - (H[i] + 1) + 1;
                    }
                }
            }
            else
            {
                onsen o = *it;
                while (1)
                {
                    onsen now = *st.begin();
                    st.erase(st.begin());
                    if (now.c == 0)
                    {
                        ans -= now.r - now.l + 1;
                    }
                    if (now == o)
                    {
                        break;
                    }
                }
                st.insert({1, o.r, i % 2});
                if (i % 2 == 0)
                {
                    ans += o.r;
                }
            }
        }
        cout << ans << "\n";
    }
}
0