結果
| 問題 |
No.3017 交互浴
|
| コンテスト | |
| ユーザー |
miscalc
|
| 提出日時 | 2025-09-29 18:43:57 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 335 ms / 2,000 ms |
| コード長 | 2,687 bytes |
| コンパイル時間 | 3,567 ms |
| コンパイル使用メモリ | 289,964 KB |
| 実行使用メモリ | 11,008 KB |
| 最終ジャッジ日時 | 2025-09-29 18:44:16 |
| 合計ジャッジ時間 | 18,532 ms |
|
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 55 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define vc pmr::vector
using vl = vc<ll>;
#define ov(a, b, c, name, ...) name
#define rep2(i, l, r) for(ll i = (l); i < ll(r); i++)
#define rep1(i, n) rep2(i, 0, n)
#define rep(...) ov(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define fec(...) for(const auto& __VA_ARGS__)
#define per(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define ALL(x) begin(x), end(x)
#define SZ(x) (ll) size(x)
#define LB(v, x) (lower_bound(ALL(v), x) - begin(v))
#define eb emplace_back
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
const ll INF = ll(4e18) + 100;
void printvec(const auto& v) {
for(auto it = begin(v); it != end(v); it++) cout << *it << " ";
cout << endl;
}
#ifdef LOCAL
#define local(...) __VA_ARGS__
#else
#define local(...)
#endif
template<class T> struct IntervalMap {
map<ll, T> mp; // mp[左端] = 区間の値
// 初期化: 興味のある区間 [l, r) と使わない値 x
// 最初はすべて x で埋める、コンストラクタを呼んだ後適切に update する
IntervalMap(ll l, ll r, T x) { mp[l - 1] = mp[r] = x; }
// 添字 k が属する連の (l, r, x)
auto get(ll k) {
auto it = prev(mp.upper_bound(k));
return tuple{it->first, next(it)->first, it->second};
}
// [l, r) を x にし、追加・削除ごとに add(L, R, X), del(L, R, X) を呼ぶ
// add は L==R が呼ばれることもあるので注意
void update(ll l, ll r, T x, auto add, auto del) {
fec(b : {l, r}) {
auto [a, c, v] = get(b);
del(a, c, v), mp[b] = v, add(a, b, v), add(b, c, v);
}
for(auto it = mp.find(l); it->first != r; it = mp.erase(it)) {
del(it->first, next(it)->first, it->second);
}
if(auto it = mp.find(r); it->second == x) {
del(it->first, next(it)->first, it->second);
mp.erase(it);
}
auto [a, b, v] = get(l);
if(v == x) del(a, l, x), add(a, b, x);
else mp[l] = x, add(l, b, x);
}
};
void main2() {
ll N;
cin >> N;
vl H(N);
rep(i, N) cin >> H.at(i);
IntervalMap<ll> im(-1, INF, -1);
ll ans = 0;
auto add = [&](ll l, ll r, ll x) {
if(x == 1) ans += r - l;
};
auto del = [&](ll l, ll r, ll x) {
if(x == 1) ans -= r - l;
};
im.update(0, INF, 0, add, del);
rep(i, N) {
im.update(0, H.at(i), (i + 1) % 2, add, del);
cout << ans << "\n";
}
}
int main() {
#ifndef LOCAL
cin.tie(0)->sync_with_stdio(0);
#endif
local(while(true)) {
ll t = 1;
// cin >> t;
while(t--) main2();
}
}
miscalc