結果
問題 | No.3017 交互浴 |
ユーザー |
![]() |
提出日時 | 2025-01-25 14:39:47 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 281 ms / 2,000 ms |
コード長 | 3,564 bytes |
コンパイル時間 | 3,380 ms |
コンパイル使用メモリ | 284,132 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2025-01-25 23:25:50 |
合計ジャッジ時間 | 13,626 ms |
ジャッジサーバーID (参考情報) |
judge8 / judge11 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 55 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #ifdef LOCAL #include <debug.hpp> #else #define debug(...) #endif // https://codeforces.com/contest/1638/problem/E // 持つ値のタイプ T、座標タイプ X // コンストラクタでは T none_val を指定する template <typename T, typename X = ll> struct Intervals { static constexpr X LLIM = numeric_limits<X>::lowest(); static constexpr X RLIM = numeric_limits<X>::max(); T none_val; // const T none_val; // none_val でない区間の個数と長さ合計 int total_num; X total_len; map<X, T> dat; Intervals(T none_val) : none_val(none_val), total_num(0), total_len(0) { dat[LLIM] = none_val; dat[RLIM] = none_val; } // x を含む区間の情報の取得 l, r, t tuple<X, X, T> get(X x, bool ERASE = false) { auto it2 = dat.upper_bound(x); auto it1 = prev(it2); auto [l, tl] = *it1; auto [r, tr] = *it2; if (tl != none_val && ERASE) { --total_num, total_len -= r - l; dat[l] = none_val; merge_at(l); merge_at(r); } return {l, r, tl}; } // [L, R) 内の全データの取得 f(l, r, t) template <typename F> void enumerate_range(X L, X R, F f, bool ERASE = false) { assert(LLIM <= L && L <= R && R <= RLIM); if (!ERASE) { auto it = prev(dat.upper_bound(L)); while ((*it).first < R) { auto it2 = next(it); f(max((*it).first, L), min((*it2).first, R), (*it).second); it = it2; } return; } // 半端なところの分割 auto p = prev(dat.upper_bound(L)); if ((*p).first < L) { dat[L] = (*p).second; if (dat[L] != none_val) ++total_num; } p = dat.lower_bound(R); if (R < (*p).first) { T t = (*prev(p)).second; dat[R] = t; if (t != none_val) ++total_num; } p = dat.lower_bound(L); while (1) { if ((*p).first >= R) break; auto q = next(p); T t = (*p).second; f((*p).first, (*q).first, t); if (t != none_val) --total_num, total_len -= (*q).first - (*p).first; p = dat.erase(p); } dat[L] = none_val; } void set(X L, X R, T t) { assert(L <= R); if (L == R) return; enumerate_range(L, R, [](int l, int r, T x) -> void {}, true); dat[L] = t; if (t != none_val) total_num++, total_len += R - L; merge_at(L); merge_at(R); } template <typename F> void enumerate_all(F f) { enumerate_range(LLIM, RLIM, f, false); } void merge_at(X p) { if (p == LLIM || RLIM == p) return; auto itp = dat.lower_bound(p); assert((*itp).first == p); auto itq = prev(itp); if ((*itp).second == (*itq).second) { if ((*itp).second != none_val) --total_num; dat.erase(itp); } } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); int N; cin >> N; vector<int> H(N); for (int i = 0; i < N; i++) cin >> H[i]; Intervals<int, int> I(0); for (int i = 0; i < N; i++) { if (i & 1) { I.set(0, H[i], 0); // 緑 } else { I.set(0, H[i], 1); // 水色 } cout << I.total_len << "\n"; } }