結果

問題 No.631 Noelちゃんと電車旅行
コンテスト
ユーザー paruki
提出日時 2018-01-05 21:52:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 305 ms / 2,000 ms
コード長 3,160 bytes
コンパイル時間 1,949 ms
コンパイル使用メモリ 173,964 KB
実行使用メモリ 7,680 KB
最終ジャッジ日時 2024-10-02 09:26:48
合計ジャッジ時間 7,111 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

template<class Val, class Cmp, Val DEF>
struct LazySegtreeRMQ {
    int dataSize, givenL, givenR;
    vector<Val> lazy, dat;
    Cmp cmp;
    LazySegtreeRMQ(int n) {
        dataSize = 1;
        while (dataSize < n)dataSize *= 2;
        dat = lazy = vector<Val>(dataSize * 2, DEF);
    }
    void propagate(int index, int curL, int curR) {
        // 自分の値をlazyにもとづいて書き換えて自分のlazyをクリア。
        // 子のlazyを書き換える。
        if (lazy[index] != DEF) {
            dat[index] += lazy[index];
            if (curR - curL > 1) {
                lazy[index * 2] += lazy[index];
                lazy[index * 2 + 1] += lazy[index];
            }
            lazy[index] = DEF;
        }
    }

    // [curL, curR) を評価する
    void update(int index, int curL, int curR, Val x) {
        // 範囲外であろうとpropagateは必ず呼ぶ。そうでないと、親がうまく評価されない
        propagate(index, curL, curR);
        if (givenL <= curL && curR <= givenR) {
            lazy[index] = x;
            // 直接書き換えないでindexのlazyを書き換えてpropagateを呼ぶ
            propagate(index, curL, curR);
        } else if (curR > givenL && givenR > curL) {
            int mid = (curL + curR) / 2, lc = index * 2, rc = lc + 1;
            update(lc, curL, mid, x);
            update(rc, mid, curR, x);
            dat[index] = cmp(dat[lc], dat[rc]) ? dat[lc] : dat[rc];
        }
    }

    void update(int l, int r, Val x) {
        givenL = l;
        givenR = r;
        update(1, 0, dataSize, x);
    }

    Val query(int l, int r) {
        givenL = l;
        givenR = r;
        return query(1, 0, dataSize);
    }

    Val query(int index, int curL, int curR) {
        // 範囲外
        if (curR <= givenL || givenR <= curL)return DEF;
        propagate(index, curL, curR);
        if (givenL <= curL && curR <= givenR) {
            return dat[index];
        } else {
            Val lv = query(index * 2, curL, (curL + curR) / 2);
            Val rv = query(index * 2 + 1, (curL + curR) / 2, curR);
            return cmp(lv, rv) ? lv : rv;
        }
    }
};

int N, T[100005], M;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> N;
    rep(i, N - 1)cin >> T[i];

    LazySegtreeRMQ<ll, greater<ll>, 0> rmq(N - 1);
    rep(i, N - 1) {
        rmq.update(i, i+1, T[i] + (N - 1-i) * 3);
    }

    cin >> M;
    rep(i, M) {
        int L, R, D;
        cin >> L >> R >> D;
        --L;
        rmq.update(L, R, D);
        cout << rmq.query(0, N - 1) << endl;
    }
}
0