結果

問題 No.1000 Point Add and Array Add
コンテスト
ユーザー NOSS
提出日時 2020-02-28 22:29:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 303 ms / 2,000 ms
コード長 1,463 bytes
コンパイル時間 1,470 ms
コンパイル使用メモリ 170,552 KB
実行使用メモリ 11,520 KB
最終ジャッジ日時 2024-10-13 17:58:05
合計ジャッジ時間 5,699 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;
using P = pair<int, int>;
using P3 = pair<int, P>;
using PP = pair<P, P>;
constexpr int INF = 1 << 30;
constexpr ll MOD = ll(1e9) + 7;
constexpr int di[] = {0, 1, 0, -1};
constexpr int dj[] = {1, 0, -1, 0};

int N=1, Q;
vector<ll> A, B, lazy;

void eval(int k){
    if(lazy[k]>0){
        if(k < N-1){
            lazy[k*2+1] += lazy[k];
            lazy[k*2+2] += lazy[k];
        }else{
            B[k-(N-1)] += A[k-(N-1)]*lazy[k];
        }
        lazy[k] = 0;
    }
}

void add(int x, int y, int k=0, int l=0, int r=N){
    if(y <= l || r <= x) return;
    if(x <= l && r <= y) lazy[k]++;
    else{
        add(x,y,k*2+1,l,(l+r)/2);
        add(x,y,k*2+2,(l+r)/2,r);
    }
}

void update(int x, ll y, int k=0, int l=0, int r=N){
    if(x < l || x >= r) return;
    eval(k);
    if(k<N-1){
        update(x,y,k*2+1,l,(l+r)/2);
        update(x,y,k*2+2,(l+r)/2,r);
    }else{
        A[x] += y;
    }
}


int main() {
    int n;
    cin >> n >> Q;
    while(N<n) N<<=1;
    A.resize(N,0);
    B.resize(N,0);
    lazy.resize(N*2,0);
    for(int i=0;i<n;i++){
        cin >> A[i];
    }
    for(int i=0;i<Q;i++){
        char c;
        ll x, y;
        cin >> c >> x >> y;
        x--;
        if(c=='A') update(x,y);
        else add(x,y);
    }
    for(int i=0;i<n;i++){
        update(i,0);
    }
    for(int i=0;i<n;i++){
        cout << B[i] << " \n"[i==n-1];
    }
    return 0;
}
0