結果

問題 No.631 Noelちゃんと電車旅行
ユーザー TangentDay
提出日時 2018-01-05 22:45:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 361 ms / 2,000 ms
コード長 2,693 bytes
コンパイル時間 938 ms
コンパイル使用メモリ 90,384 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-02 09:27:25
合計ジャッジ時間 6,413 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:105:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  105 |         scanf("%lld", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~~~
main.cpp:118:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  118 |         scanf("%lld %lld %lld", &l, &r, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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