結果

問題 No.631 Noelちゃんと電車旅行
ユーザー algon_320algon_320
提出日時 2018-01-05 22:55:19
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 396 ms / 2,000 ms
コード長 4,586 bytes
コンパイル時間 2,386 ms
コンパイル使用メモリ 183,464 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2024-04-10 07:45:48
合計ジャッジ時間 8,901 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 261 ms
6,812 KB
testcase_01 AC 377 ms
10,240 KB
testcase_02 AC 388 ms
10,240 KB
testcase_03 AC 396 ms
10,240 KB
testcase_04 AC 378 ms
10,240 KB
testcase_05 AC 387 ms
10,368 KB
testcase_06 AC 150 ms
6,940 KB
testcase_07 AC 89 ms
6,944 KB
testcase_08 AC 301 ms
9,984 KB
testcase_09 AC 326 ms
6,944 KB
testcase_10 AC 248 ms
9,984 KB
testcase_11 AC 216 ms
6,944 KB
testcase_12 AC 281 ms
10,112 KB
testcase_13 AC 237 ms
6,940 KB
testcase_14 AC 104 ms
6,940 KB
testcase_15 AC 201 ms
6,940 KB
testcase_16 AC 2 ms
6,940 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v)) os<<*i<<(i==end(v)-1?"":" "); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i; return is; }
template<class T,class U> istream& operator >> (istream &is, pair<T,U> &p) {
    is>>p.first>>p.second; return is; }
template <class T> bool chmax(T &a,const T &b) {if(a<b) {a=b;return 1;} return 0;}
template <class T> bool chmin(T &a,const T &b) {if(b<a) {a=b;return 1;} return 0;}
template <class T> using heap = priority_queue<T,vector<T>,greater<T>>;
struct { template <typename T> operator T() { T x; cin >> x; return x; } } IN;
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

template <class T>
struct LazySegmentTree {
    using func = function<T(T, T)>;
    int size;
    vector<T> data;
    vector<T> lazy;
    vector<T> width;
    function<T(T,T,int)> updater;
    func merger, propagater;
    T ident_prop, ident_query;

    LazySegmentTree(int n, function<T(T,T,int)> update_func, func merge_func,
      func propagate_func, T identity_propagate, T identity_query)
      : updater(update_func), merger(merge_func), propagater(propagate_func),
      ident_prop(identity_propagate), ident_query(identity_query) {
        size = 1;
        while (size < n) size <<= 1;
        data.resize(size*2, ident_query);
        lazy.resize(size*2, ident_prop);
        width.resize(size*2, 1);
        for (int i = size-2; i >= 0; i--) {
            width[i] = width[i*2+1] + width[i*2+2];
        }
    }
    void lazy_propagate(int p) {
        data[p] = updater(data[p], lazy[p], width[p]);
        if (p < size-1) {
            lazy[p*2+1] = propagater(lazy[p*2+1], lazy[p]);
            lazy[p*2+2] = propagater(lazy[p*2+2], lazy[p]);
        }
        lazy[p] = ident_prop;
    }
    void update(int wishL, int wishR, int x, int watchL = 0, int watchR = -1, int k = 0) {
        if (watchR == -1) watchR = size;
        if (wishR <= watchL || watchR <= wishL) {
            lazy_propagate(k);
            return;
        }
        if (wishL <= watchL && watchR <= wishR) {
            lazy[k] = propagater(lazy[k], x);
            lazy_propagate(k);
            return;
        }

        int mid = (watchL+watchR)/2;
        lazy_propagate(k);
        update(wishL, wishR, x, watchL, mid, k*2+1);
        update(wishL, wishR, x, mid, watchR, k*2+2);
        data[k] = merger(data[k*2+1], data[k*2+2]);
    }
    T query(int wishL, int wishR, int watchL = 0, int watchR = -1, int k = 0) {
        if (watchR == -1) watchR = size;
        if (watchR <= wishL || wishR <= watchL) return ident_query;
        if (wishL <= watchL && watchR <= wishR) {
            lazy_propagate(k);
            return data[k];
        }
        lazy_propagate(k);
        T ld = query(wishL, wishR, watchL, (watchL+watchR)/2, k*2+1);
        T rd = query(wishL, wishR, (watchL+watchR)/2, watchR, k*2+2);
        return merger(ld, rd);
    }
};
signed main() {
    int N=IN;
    vector<int> T(N-1);
    cin>>T;
    auto update=[](int a,int b,int w) {return a+b;};
    auto merge=[](int a,int b) {return min(a,b);};
    auto propagate=[](int a,int b) {return a+b;};
    LazySegmentTree<int> seg(N,update,merge,propagate,0,INF);
    seg.update(0,N,-INF);
    int sum=0;
    REP(i,N-1) {
        seg.update(i,i+1,sum-T[i]);
        sum+=3;
    }

    int M=IN;
    REP(i,M) {
        int L=IN,R=IN,D=IN;
        seg.update(L-1,R,-D);
        cout<<(sum-seg.query(0,N))<<endl;
    }
    return 0;
}
0