結果

問題 No.3017 交互浴
ユーザー srjywrdnprkt
提出日時 2025-03-13 00:46:31
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 330 ms / 2,000 ms
コード長 2,124 bytes
コンパイル時間 3,534 ms
コンパイル使用メモリ 280,336 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-13 00:46:57
合計ジャッジ時間 23,391 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       水色である区間[l, r]をスタックで管理。
       後ろのものほど区間として先に出てくる。
       水色の温泉に入ったとき、r<=Hであるものは削除。l<=H<rであるものがでてきたら[1, r]にする。H<lなら[1, H]を追加
       緑色の温泉に入ったとき、r<=Hであるものは削除。l<=H<r-1であるものがでてきたら[H+1, r]にする。H<lなら何もしない。
    */

    int N, l, r, H, ans=0;
    cin >> N;
    vector<pair<int, int>> v;
    for (int i=0; i<N; i++){
        cin >> H;
        if (i % 2 == 0){
            while(!v.empty()){
                tie(l, r) = v.back();
                if (r<=H){
                    v.pop_back();
                    ans -= r-l+1;
                }
                else break;
            }
            if (!v.empty()){
                tie(l, r) = v.back();
                if (l<=H && H<r){
                    v.pop_back();
                    ans -= r-l+1;
                    v.push_back({1, r});
                    ans += r;
                }
                else{
                    v.push_back({1, H});
                    ans += H;
                }
            }
            else{
                v.push_back({1, H});
                ans += H;
            }
        }
        else{
            while(!v.empty()){
                tie(l, r) = v.back();
                if (r<=H){
                    v.pop_back();
                    ans -= r-l+1;
                }
                else break;
            }
            if (!v.empty()){
                tie(l, r) = v.back();
                if (l<=H && H<r){
                    v.pop_back();
                    ans -= r-l+1;
                    v.push_back({H+1, r});
                    ans += r-H;
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}
0