結果

問題 No.631 Noelちゃんと電車旅行
ユーザー paruki
提出日時 2018-01-05 21:52:18
言語 C++14
(gcc 8.2.0)
結果
AC  
実行時間 455 ms
コード長 3,160 Byte
コンパイル時間 1,894 ms
使用メモリ 5,780 KB
最終ジャッジ日時 2018-11-12 15:03:33

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
LEARGE_case1.txt AC 455 ms
5,780 KB
LEARGE_case2.txt AC 453 ms
5,776 KB
LEARGE_case3.txt AC 446 ms
5,776 KB
LEARGE_case4.txt AC 452 ms
5,780 KB
LEARGE_case5.txt AC 443 ms
5,780 KB
RANDOM_case1.txt AC 171 ms
3,660 KB
RANDOM_case2.txt AC 86 ms
3,668 KB
RANDOM_case3.txt AC 330 ms
5,776 KB
RANDOM_case4.txt AC 392 ms
3,664 KB
RANDOM_case5.txt AC 270 ms
5,776 KB
RANDOM_case6.txt AC 238 ms
3,664 KB
RANDOM_case7.txt AC 298 ms
5,776 KB
RANDOM_case8.txt AC 291 ms
2,612 KB
RANDOM_case9.txt AC 135 ms
1,608 KB
RANDOM_case10.txt AC 248 ms
2,612 KB
SMALL_case1.txt AC 1 ms
1,540 KB
SMALL_case2.txt AC 3 ms
1,544 KB
SMALL_case3.txt AC 3 ms
1,540 KB
SMALL_case4.txt AC 3 ms
1,544 KB
SMALL_case5.txt AC 2 ms
1,544 KB
テストケース一括ダウンロード

ソースコード

diff #
#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