結果
問題 |
No.3017 交互浴
|
ユーザー |
|
提出日時 | 2025-07-02 23:50:43 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 481 ms / 2,000 ms |
コード長 | 5,187 bytes |
コンパイル時間 | 3,786 ms |
コンパイル使用メモリ | 284,972 KB |
実行使用メモリ | 10,880 KB |
最終ジャッジ日時 | 2025-07-02 23:51:11 |
合計ジャッジ時間 | 26,745 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 55 |
ソースコード
#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 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()) template <class S, class T> struct Intervals { static constexpr S INF = numeric_limits<S>::max() / 2; static constexpr S L = -INF, R = INF; T none_val; // 区間の色を表す ll total_num; // none_val でない区間の個数 S total_len; // none_val でない区間の長さの合計 map<S, T> data; // コンストラクタ:全体[L, R) を none_val に初期化 Intervals(T nv = -1) : none_val(nv), total_num(0), total_len(0) { data.em(L, none_val); data.em(R, none_val); } // 区間 [l, r) の値を v に設定 void set(S l, S r, T v) { assert(L <= l && r <= R); if (l >= r) return; auto it_l = split(l), it_r = split(r); // [l, r) に含まれる既存の区間をすべて削除 for (auto it = it_l; it != it_r;) { if (it->second != none_val) { S seg_l = it->first, seg_r = next(it)->first; total_len -= (seg_r - seg_l); --total_num; } // 消しつつ前へ進める it = data.erase(it); } // 新たに区間を挿入 auto it = data.em(l, v).first; if (v != none_val) { total_len += (r - l); ++total_num; } // 左側との結合 if (it != data.begin()) { auto it_prev = prev(it); if (it_prev->second == v) { data.erase(it); --total_num; l = it_prev->first; it = it_prev; } } // 右側との結合 auto it_next = next(it); if (it_next != data.end() && it_next->second == v) { data.erase(it_next); --total_num; } } // 点 i が含まれる [i, i + 1) の値を返す T get_value(S i) { auto it = prev(data.upper_bound(i)); return it->second; } // 点 i が含まれる区間 [l, r) とその値 v を返す tuple<S, S, T> get(S i) { assert(L <= i && i < R); auto it_r = data.upper_bound(i), it_l = prev(it_r); return make_tuple(it_l->first, it_r->first, it_l->second); } // 区間 [l, r) 内の区間を(境界ごとに分割した) run-length 圧縮結果として返す vector<tuple<S, S, T>> get(S l, S r) { assert(L <= l && r <= R); vector<tuple<S, S, T>> res; if (l >= r) return res; auto it_r = data.upper_bound(l), it_l = prev(it_r); while (it_l->first < r) { res.emplace_back(max(l, it_l->first), min(it_r->first, r), it_l->second); it_l = it_r++; } return res; } private: // 点 pos において区間を分割し,すでに境界があればその位置のイテレータを返す // そうでなければ,その区間 [l, r) を [l, pos) と [pos, r) に分割し,後者の先頭を返す typename map<S, T>::iterator split(S pos) { auto it = data.lower_bound(pos); if (it != data.end() && it->first == pos) return it; T v = prev(it)->second; auto res = data.emplace(pos, v).first; if (v != none_val) total_num++; return res; } }; void solve() { ll n; cin >> n; vl h(n); cin >> h; Intervals<ll, ll> I(0); rep(i, n) { I.set(0, h[i], ((i & 1) ^ 1ll)); cout << I.total_len << 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; }