結果

問題 No.1000 Point Add and Array Add
ユーザー tactac
提出日時 2020-02-28 22:07:48
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 293 ms / 2,000 ms
コード長 3,840 bytes
コンパイル時間 2,243 ms
コンパイル使用メモリ 176,748 KB
実行使用メモリ 16,948 KB
最終ジャッジ日時 2023-08-03 20:35:29
合計ジャッジ時間 6,679 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 1 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 3 ms
4,380 KB
testcase_13 AC 2 ms
4,380 KB
testcase_14 AC 4 ms
4,380 KB
testcase_15 AC 4 ms
4,376 KB
testcase_16 AC 200 ms
15,820 KB
testcase_17 AC 168 ms
10,592 KB
testcase_18 AC 293 ms
16,888 KB
testcase_19 AC 293 ms
16,816 KB
testcase_20 AC 188 ms
16,800 KB
testcase_21 AC 282 ms
16,948 KB
testcase_22 AC 238 ms
16,844 KB
testcase_23 AC 289 ms
16,820 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { rep(i, sz(vec)) { if (i) os << " "; os << vec[i]; } return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int T;
  // cin >> T;
  T = 1;

  while (T--) {
      solve();
  }
}

struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;

public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }

    void eval(int k, int l, int r) {
        if(lazy[k] != 0) {
            node[k] += lazy[k];
            if(r - l > 1) {
                lazy[2*k+1] += lazy[k] / 2;
                lazy[2*k+2] += lazy[k] / 2;
            }
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }
        else {
            add(a, b, x, 2*k+1, l, (l+r)/2);
            add(a, b, x, 2*k+2, (l+r)/2, r);
            node[k] = node[2*k+1] + node[2*k+2];
        }
    }

    ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
        if(r < 0) r = n;
        eval(k, l, r);
        if(b <= l || r <= a) return 0;
        if(a <= l && r <= b) return node[k];
        ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
        ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
        return vl + vr;
    }


};


void solve() {
  int n, q;
  cin >> n >> q;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  vector<char> c(q);
  vector<int> x(q), y(q);
  rep(i, q) {
    cin >> c[i] >> x[i] >> y[i];
    x[i]--;
  }

  vector<int> e(n); // そこが何回足されるか
  rep(i, q) {
    if (c[i] == 'B') {
      e[x[i]]++;
      e[y[i]]--;
    }
  }
  rep(i, n - 1) e[i + 1] += e[i];

  LazySegmentTree seg(vector<ll>(n, 0)); // そこが何回足されたか

  vector<ll> b(n + 1);
  rep(i, q) {
    if (c[i] == 'A') {
      ll tmp = 1LL * (e[x[i]] - seg.getsum(x[i], x[i] + 1)) * y[i];
      b[x[i]] += tmp;
    } else {
      seg.add(x[i], y[i], 1);
    }
  }

  // rep(i, n) cout << seg.getsum(i, i + 1) << " "; cout << endl;
  // cout << b << endl;
  rep(i, n) b[i] += 1LL * seg.getsum(i, i + 1) * a[i];
  b.pop_back();
  cout << b << endl;

}
0