結果

問題 No.631 Noelちゃんと電車旅行
ユーザー 0w10w1
提出日時 2018-09-27 17:09:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 282 ms / 2,000 ms
コード長 1,580 bytes
コンパイル時間 2,645 ms
コンパイル使用メモリ 210,672 KB
実行使用メモリ 7,792 KB
最終ジャッジ日時 2024-10-02 09:39:15
合計ジャッジ時間 7,619 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 225 ms
7,296 KB
testcase_01 AC 278 ms
7,680 KB
testcase_02 AC 277 ms
7,680 KB
testcase_03 AC 274 ms
7,792 KB
testcase_04 AC 282 ms
7,680 KB
testcase_05 AC 280 ms
7,680 KB
testcase_06 AC 113 ms
7,424 KB
testcase_07 AC 62 ms
7,552 KB
testcase_08 AC 208 ms
7,680 KB
testcase_09 AC 247 ms
7,448 KB
testcase_10 AC 167 ms
7,552 KB
testcase_11 AC 153 ms
7,552 KB
testcase_12 AC 187 ms
7,552 KB
testcase_13 AC 186 ms
7,296 KB
testcase_14 AC 93 ms
7,296 KB
testcase_15 AC 156 ms
7,424 KB
testcase_16 AC 5 ms
7,296 KB
testcase_17 AC 5 ms
7,296 KB
testcase_18 AC 5 ms
7,168 KB
testcase_19 AC 5 ms
7,296 KB
testcase_20 AC 5 ms
7,296 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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