結果

問題 No.3017 交互浴
ユーザー みねしみねみね
提出日時 2025-06-29 22:32:06
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,204 bytes
コンパイル時間 6,262 ms
コンパイル使用メモリ 335,196 KB
実行使用メモリ 11,144 KB
最終ジャッジ日時 2025-06-29 22:32:35
合計ジャッジ時間 28,814 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 2 WA * 53
権限があれば一括ダウンロードができます

ソースコード

diff # 

#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG//[]で配列外参照をするとエラーにしてくれる。上下のやつがないとTLEになるので注意 ABC311Eのサンプル4みたいなデバック中のTLEは防げないので注意
#endif
#include <bits/stdc++.h>
#include <algorithm>
#include <cmath> // M_PIを使用するため
#include <atcoder/all>
using namespace std;
using namespace atcoder;

using ll = long long;
using ld = long double;
#define rep(i,n) for (ll i = 0; i < (ll)(n); i++)
#define rrep(i,n) for (ll i = (ll)n - 1; i >= 0; --i)

const ll INF = (1LL << 62);
const ll null = -1LL;
template<typename T> using vc = vector<T>;//prioriy_queueに必要なのでここにこれ書いてます
template<typename T> using vv = vc<vc<T>>;
template<typename T> using vvv = vv<vc<T>>;
using vl = vc<ll>; using vvl = vv<ll>; using vvvl = vv<vl>; using vvvvl = vv<vvl>;
using vs = vc<string>; using vvs = vv<string>;
using vb = vc<bool>; using vvb = vc<vb>;
using P = pair<ll , ll>;

template<class T>istream& operator>>(istream& i, vc<T>& v) { rep(j, size(v))i >> v[j]; return i; }
// それぞれ「下，上，右，左」に対応
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

#define nall(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()

#define chmax(x,y) x = max(x,y)
#define chmin(x,y) x = min(x,y)

#define pb push_back
#define eb emplace_back
#define em emplace
#define pob pop_back
#define next_p(v) next_permutation(v.begin(),v.end())

void solve() {
    ll n; cin >> n;
    vl h(n); cin >> h;
    priority_queue<P, vc<P>, greater<>> pq;
    ll ans = 0;
    rep(i,n) {
        if ((i & 1ll) == 0) {
            // cyan
            ll pre = 0;
            while (pq.size()) {
                auto [height, col] = pq.top();
                if (height >= h[i]) {
                    if (col == 0) {
                        // green
                        ans += h[i] - pre;
                    }
                    pre = height;
                    break;
                }
                pq.pop();
                if (col == 1) {
                    pre = height;
                } else {
                    ans += height - pre;
                    pre = height;
                }
            }
            ans += max(h[i] - pre, 0ll);
        } else {
            // green
            ll pre = 0;
            while (pq.size()) {
                auto [height, col] = pq.top();
                if (height >= h[i]) {
                    if (col == 1) {
                        // cyan
                        ans -= h[i] - pre;
                    }
                    pre = height;
                    break;
                }
                pq.pop();
                if (col == 0) {
                    pre = height;
                } else {
                    ans -= height - pre;
                    pre = height;
                }
            }
            ans -= max(h[i] - pre, 0ll);
        }
        cout << ans << endl;
        pq.em(h[i], (i & 1ll) == 0);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.tie(0);
    ll testcases = 1ll;
    // cin >> testcases;
    rep(_,testcases) solve();
    
    return 0;
}
0