結果

問題 No.631 Noelちゃんと電車旅行
コンテスト
ユーザー 0w1
提出日時 2018-09-27 17:09:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 339 ms / 2,000 ms
コード長 1,580 bytes
コンパイル時間 2,482 ms
コンパイル使用メモリ 204,116 KB
最終ジャッジ日時 2025-01-06 13:48:01
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

template<int nn>
struct Segt {
  vector<int64_t> maxv;
  vector<int64_t> addv;
  Segt() {
    assert(__builtin_popcount(nn) == 1);
    maxv.assign(nn, 0);
    addv.assign(nn, 0);
  }
  void push(int t) {
    for (int c = 0; c < 2; ++c) {
      maxv[t << 1 | c] += addv[t];
      addv[t << 1 | c] += addv[t];
    }
    addv[t] = 0;
  }
  void pull(int t) {
    maxv[t] = max(maxv[t << 1], maxv[t << 1 | 1]);
  }
  void modify(int ql, int qr, int v, int t = 1, int lb = 0, int rb = nn / 2) {
    if (qr <= lb || rb <= ql) return;
    if (ql <= lb && rb <= qr) {
      maxv[t] += v;
      addv[t] += v;
      return;
    }
    push(t);
    int mb = lb + rb >> 1;
    modify(ql, qr, v, t << 1, lb, mb);
    modify(ql, qr, v, t << 1 | 1, mb, rb);
    pull(t);
  }
  int64_t query(int ql, int qr, int t = 1, int lb = 0, int rb = nn / 2) {
    if (qr <= lb || rb <= ql) return -1LL << 60;
    if (ql <= lb && rb <= qr) return maxv[t];
    push(t);
    int mb = lb + rb >> 1;
    return max(query(ql, qr, t << 1, lb, mb), query(ql, qr, t << 1 | 1, mb, rb));
  }
};

signed main() {
  ios::sync_with_stdio(false);

  int N;
  cin >> N;

  vector<int> T(N - 1);
  for (int i = 0; i < N - 1; ++i) cin >> T[i];

  Segt<1 << 18> tree;
  for (int i = 0; i < N - 1; ++i) tree.modify(i, i + 1, T[i] - 3LL * i);

  int M;
  cin >> M;

  for (int i = 0; i < M; ++i) {
    int L, R, D;
    cin >> L >> R >> D;
    tree.modify(L - 1, R, D);
    int64_t maxv = tree.query(0, N - 1);
    int64_t ans = maxv + 3LL * (N - 1);
    cout << ans << endl;
  }
}
0