結果

問題 No.3017 交互浴
コンテスト
ユーザー ZOI-dayo
提出日時 2025-02-22 03:12:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 749 ms / 2,000 ms
コード長 1,302 bytes
コンパイル時間 4,147 ms
コンパイル使用メモリ 292,908 KB
実行使用メモリ 20,868 KB
最終ジャッジ日時 2025-02-22 03:13:24
合計ジャッジ時間 41,124 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 55
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/lazysegtree.hpp>
using namespace atcoder;

#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)

#define chmin(x, y) x = min(x, y)
// #include <all.hpp>

// #define int long long

struct T {
  int val;
  int size;
};

T op(T a, T b) {
  return T{
    a.val + b.val,
    a.size + b.size
  };
}

T e() {
  return {0,0};
}

T mapping(int f, T x) {
  if(f < 0) return x;
  return T{
    f * x.size,
    x.size
  };
}

int composition(int f, int g) {
  if(f == -1) return g;
  return f;
}

int id() {
  return -1;
}

signed main() {
  int n;
  cin >>n ;
  vector<int> h(n);

  rep(i, n) cin >> h[i];
  auto hh = h;
  sort(hh.begin(), hh.end());
  hh.erase(unique(hh.begin(), hh.end()), hh.end());
  map<int, int> mp;
  rep(i, hh.size()) mp[hh[i]] = i;
  vector<T> src(hh.size());
  rep(i, hh.size()) {
    src[i] = T{
      0,
      hh[i] - (i == 0 ? 0 : hh[i-1])
    };
  }
  lazy_segtree<T, op, e, int, mapping, composition, id> seg(src);
  rep(i, n) {
    // cout << 0 << " " << mp[h[i]] + 1 << " " << 1 - i%2 << endl;
    seg.apply(0, mp[h[i]]+1, 1 - i%2);
    cout << seg.all_prod().val << endl;
  }
  /*
  int ans = 0;
  rep(i, hh.size()+1) {
    if(seg.get(i)) {
      ans += hh[i] - (i == 0 ? 0 :hh[i-1]);
    }
  }
  cout << ans << endl;
  */
}
0