結果

問題 No.3017 交互浴
コンテスト
ユーザー 小高悠太郎
提出日時 2025-09-04 17:11:40
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 695 ms / 2,000 ms
コード長 1,612 bytes
コンパイル時間 4,296 ms
コンパイル使用メモリ 293,248 KB
実行使用メモリ 21,908 KB
最終ジャッジ日時 2025-09-04 17:12:27
合計ジャッジ時間 43,126 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i< (n); ++i)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define all(x) (x).begin(), (x).end()
#define fore(i, a) for(auto &i:a)
using ll = long long;
#include<atcoder/lazysegtree>
using namespace atcoder;

struct S{
	ll value;
	ll size;
};
struct F{
	ll value;
	bool flag;
};
S op(S l, S r){
	return S{l.value+r.value, l.size+r.size};
}
S e(){
	return S{0,0};
}
S mapping(F f, S x){
	if(f.flag){
		return S{f.value*x.size, x.size};
	}
	else{
		return x;
	}
}
F composition(F f, F g){
	if(f.flag){
		return f;
	}
	else{
		return g;
	}
}
F id(){
	return F{0,false};
}
template<typename T=int>
struct CC {
	bool initialized;
	vector<T> xs;
	CC(): initialized(false) {}
	void add(T x) { xs.push_back(x);}
	void init() {
		sort(xs.begin(), xs.end());
		xs.erase(unique(xs.begin(),xs.end()),xs.end());
		initialized = true;
	}
	int operator()(T x) {
		if (!initialized) init();
		return upper_bound(xs.begin(), xs.end(), x) - xs.begin() - 1;
	}
	T operator[](int i) {
		if (!initialized) init();
		return xs[i];
	}
	int size() {
		if (!initialized) init();
		return xs.size();
	}
};
int main() {
  ll n; cin >> n;
  CC<ll> cc;
	vector<S> vec(n);
	vector<ll> H(n);
	rep(i, n){
		ll h;
		cin >> h;
		H[i] = h;
		cc.add(h);
	};
	cc.add(0);
	rep(i, n){
		vec[i] = {0, cc[i+1]-cc[i]};
	}
	lazy_segtree<S,op,e,F,mapping,composition,id> seg(vec);
	rep(i, n){
		seg.apply(0, cc(H[i]), {(i+1)%2, true});
		cout << seg.all_prod().value << endl;
	}
}
0