結果

問題 No.3017 交互浴
ユーザー みねしみねみね
提出日時 2025-06-30 01:04:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,439 bytes
コンパイル時間 4,051 ms
コンパイル使用メモリ 288,476 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2025-06-30 01:04:51
合計ジャッジ時間 31,654 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 WA * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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;
    ll ans = 0;
    set<tuple<ll,ll,ll>> st;
    st.em(0,INF,1);
    rep(i,n) {
        if ((i & 1ll) == 0) {
            // cyan
            bool finished = false;
            auto iter = st.begin();
            while (iter != st.end()) {
                auto [l, r, col] = *iter;
                if (h[i] < l) break;
                if (h[i] <= r) {
                    if (col) {
                        ans += h[i] - l;
                        iter = st.erase(iter);
                        st.em(h[i], r, col);
                    } else {
                        st.em(0,r,0);
                        finished = true;
                    }
                    break;
                }
                iter = st.erase(iter);
                if (col) {
                    ans += r - l;
                }
            }
            if (!finished) {
                st.em(0, h[i], 0);
            }
        } else {
            // green
            bool finished = false;
            auto iter = st.begin();
            while (iter != st.end()) {
                auto [l, r, col] = *iter;
                if (h[i] < l) break;
                if (h[i] <= r) {
                    if (col == 0) {
                        ans -= h[i] - l;
                        iter = st.erase(iter);
                        st.em(h[i], r, col);
                    } else {
                        st.em(0,r,1);
                        finished = true;
                    }
                    break;
                }
                iter = st.erase(iter);
                if (col == 0) {
                    ans -= r - l;
                }
            }
            if (!finished) {
                st.em(0, h[i], 1);
            }
        }
        cout << ans << endl;
    }
}

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