結果

問題 No.631 Noelちゃんと電車旅行
コンテスト
ユーザー vjudge1
提出日時 2025-10-19 17:03:03
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 99 ms / 2,000 ms
コード長 1,378 bytes
コンパイル時間 1,605 ms
コンパイル使用メモリ 159,732 KB
実行使用メモリ 13,664 KB
最終ジャッジ日時 2025-10-19 17:03:10
合計ジャッジ時間 6,395 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ls rt << 1
#define rs rt << 1 | 1
const int N = 5e5 + 7;
int n, m, a[N];
int val[N << 2], lazy[N << 2];
inline void pushup(int rt)
{
    val[rt] = max(val[ls], val[rs]);
    return;
}
inline void build(int l, int r, int rt)
{
    if (l == r)
    {
        val[rt] = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    pushup(rt);
}
inline void addlazy(int rt, int C)
{
    lazy[rt] += C;
    val[rt] += C;
}
inline void pushdown(int rt)
{
    if (lazy[rt])
    {
        addlazy(ls, lazy[rt]);
        addlazy(rs, lazy[rt]);
        lazy[rt] = 0;
    }
}
inline void update(int L, int R, int C, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        addlazy(rt, C);
        return;
    }
    int mid = (l + r) / 2;
    pushdown(rt);
    if (L <= mid)
        update(L, R, C, l, mid, ls);
    if (R > mid)
        update(L, R, C, mid + 1, r, rs);
    pushup(rt);
    return;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
        cin >> a[i], a[i] += 3 * (n - i);
    build(1, n, 1);
    cin >> m;
    while (m--)
    {
        int l, r, d;
        cin >> l >> r >> d;
        update(l, r, d, 1, n, 1);
        cout << val[1] << "\n";
    }
}
0