結果
問題 |
No.3017 交互浴
|
ユーザー |
|
提出日時 | 2025-02-22 02:34:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 229 ms / 2,000 ms |
コード長 | 1,379 bytes |
コンパイル時間 | 3,865 ms |
コンパイル使用メモリ | 260,656 KB |
実行使用メモリ | 18,244 KB |
最終ジャッジ日時 | 2025-02-22 02:34:49 |
合計ジャッジ時間 | 18,100 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 55 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) template<typename T> bool chmin(T &x, T y) { return x > y ? (x = y, true) : false; } template<typename T> bool chmax(T &x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); std::cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; // template atcoder lazy segtree struct S{ ll sm1=0; ll sm2=0; }; S op(S a, S b){ a.sm1+=b.sm1; a.sm2+=b.sm2; return a; } S e(){ return S{}; } using F = ll; S mapping(F f, S x){ if(f==1){ x.sm1+=x.sm2; x.sm2=0; }else if(f==2){ x.sm2+=x.sm1; x.sm1=0; } return x; } F comp(F f, F g){ if(f==0) return g; return f; } F id(){ return 0; } using segtree = atcoder::lazy_segtree<S,op,e,F,mapping,comp,id>; int main(){ int n; cin>>n; vector<int> h(n); rep(i,0,n) cin>>h[i]; auto ch=h; ch.push_back(0); sort(ch.begin(),ch.end()); ch.erase(unique(ch.begin(),ch.end()),ch.end()); int m=ch.size(); auto get_ith = [&](int x){ return lower_bound(ch.begin(),ch.end(),x)-ch.begin(); }; segtree seg(m-1); rep(i,0,m-1) seg.set(i,S{ch[i+1]-ch[i],0}); rep(i,0,n){ int j=get_ith(h[i]); if(i&1){ seg.apply(0,j,1); }else{ seg.apply(0,j,2); } auto x=seg.all_prod(); cout<<x.sm2<<"\n"; } }