結果

問題 No.631 Noelちゃんと電車旅行
ユーザー TangentDayTangentDay
提出日時 2018-01-05 22:45:52
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 379 ms / 2,000 ms
コード長 2,693 bytes
コンパイル時間 1,598 ms
コンパイル使用メモリ 85,604 KB
実行使用メモリ 4,808 KB
最終ジャッジ日時 2023-07-25 15:42:20
合計ジャッジ時間 7,255 ms
ジャッジサーバーID
(参考情報)
judge14 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 96 ms
4,384 KB
testcase_01 AC 378 ms
4,644 KB
testcase_02 AC 378 ms
4,808 KB
testcase_03 AC 378 ms
4,628 KB
testcase_04 AC 377 ms
4,700 KB
testcase_05 AC 379 ms
4,624 KB
testcase_06 AC 102 ms
4,384 KB
testcase_07 AC 75 ms
4,380 KB
testcase_08 AC 259 ms
4,672 KB
testcase_09 AC 247 ms
4,384 KB
testcase_10 AC 204 ms
4,380 KB
testcase_11 AC 181 ms
4,380 KB
testcase_12 AC 237 ms
4,632 KB
testcase_13 AC 135 ms
4,380 KB
testcase_14 AC 34 ms
4,384 KB
testcase_15 AC 138 ms
4,384 KB
testcase_16 AC 1 ms
4,380 KB
testcase_17 AC 1 ms
4,384 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 2 ms
4,380 KB
testcase_20 AC 2 ms
4,384 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

struct SqrtDecomposition{
    const ll INF = 1e18;
    int n, sqrtn, k;
    VL dat, buk, lazy;
    vector<bool> lazyflag;

    void init(int x){
        n = x;
        sqrtn = sqrt(n);
        // sqrtn = 250;
        k = (n + sqrtn - 1) / sqrtn;
        dat.assign(sqrtn * k, 0);
        buk.assign(k, 0);
        lazy.assign(k, 0);
        lazyflag.assign(k, false);
    }

    void eval(int b){
        if (!lazyflag[b]) return;
        lazyflag[b] = false;
        FOR(i, sqrtn * b, sqrtn * (b+1) - 1){
            dat[i] += lazy[b];
        }
        lazy[b] = 0;
    }

    // [l, r)
    void add(int l, int r, ll x){
        REP(b,k){
            int p = sqrtn * b;
            int q = sqrtn * (b+1);
            if (q <= l || r <= p) continue;
            if (l <= p && q <= r){
                buk[b] += x;
                lazyflag[b] = true;
                lazy[b] += x;
            }else{
                eval(b);
                FOR(i,max(l,p),min(r,q)-1){
                    dat[i] += x;
                }
                buk[b] = -INF;
                FOR(i,p,q-1){
                    buk[b] = max(buk[b], dat[i]);
                }
            }
        }
    }

    // [l, r)
    ll query(int l, int r){
        ll ret = -INF;
        REP(b,k){
            int p = sqrtn * b;
            int q = sqrtn * (b+1);
            if (q <= l || r <= p) continue;
            if (l <= p && q <= r){
                ret = max(ret, buk[b]);
            }else{
                eval(b);
                FOR(i,max(l,p),min(r,q)-1){
                    ret = max(ret, dat[i]);
                }
            }
        }
        return ret;
    }
};

int main() {
    int n;
    cin >> n;
    n--;

    VL a(n);
    REP(i,n){
        scanf("%lld", &a[i]);
        a[i] -= 3 * i;
    }

    ll s = 3 * n;
    SqrtDecomposition sd;
    sd.init(n);
    REP(i,n) sd.add(i, i+1, a[i]);

    int q;
    cin >> q;
    while (q--){
        ll l, r, d;
        scanf("%lld %lld %lld", &l, &r, &d);
        l--;r--;
        sd.add(l, r+1, d);
        printf("%lld\n", s + sd.query(0, n));
    }

    return 0;
}



0