結果

問題 No.1000 Point Add and Array Add
ユーザー tnyo43tnyo43
提出日時 2020-02-29 00:02:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 293 ms / 2,000 ms
コード長 3,305 bytes
コンパイル時間 1,922 ms
コンパイル使用メモリ 173,688 KB
実行使用メモリ 9,472 KB
最終ジャッジ日時 2024-04-21 21:06:45
合計ジャッジ時間 6,200 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 3 ms
5,376 KB
testcase_13 AC 3 ms
5,376 KB
testcase_14 AC 5 ms
5,376 KB
testcase_15 AC 4 ms
5,376 KB
testcase_16 AC 212 ms
8,448 KB
testcase_17 AC 175 ms
6,784 KB
testcase_18 AC 290 ms
9,216 KB
testcase_19 AC 293 ms
9,344 KB
testcase_20 AC 276 ms
9,472 KB
testcase_21 AC 279 ms
9,472 KB
testcase_22 AC 286 ms
9,344 KB
testcase_23 AC 282 ms
9,344 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define REPR(i,n) for (ll i = n-1; i >= 0; --i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)
#define FORR(i,m,n) for (ll i = n-1; i >= m; --i)
#define FORE(x,xs) for (const auto& x : xs)
#define ALL(v) v.begin(), v.end()
#define CHMIN(x,y) x = min(x, y)
#define CHMAX(x,y) x = max(x, y)

enum QUERY_GET { SUM, MAXIMUM, MINIMUM };
template <class T = int>
class SegmentTree {
private:
    int ARY_SIZE;
    T initVal;
    std::vector<T> ary;
    std::function<T(T&, T&)> merge;
 
    void init(int n, QUERY_GET qtype) {
        switch (qtype) {
        case SUM:
            initVal = 0;
            merge = [](T& l, T& r) {return l + r; };
            break;
        case MAXIMUM:
            initVal = std::numeric_limits<T>::lowest();
            merge = [](T& l, T& r) {return (l > r) ? l : r; };
            break;
        case MINIMUM:
            initVal = std::numeric_limits<T>::max();
            merge = [](T& l, T& r) {return (l < r) ? l : r; };
            break;
        default: struct INVALID_QUERY_TYPE_ERROR {}; throw INVALID_QUERY_TYPE_ERROR(); break;
        }
        init(n);
    }
    void init(int n) {
        while (ARY_SIZE < n) ARY_SIZE <<= 1;
        ary.resize(ARY_SIZE << 1, initVal);
    }
public:
    SegmentTree() {}
    SegmentTree(int n, QUERY_GET qtype) : ARY_SIZE(1) { init(n, qtype); }
    SegmentTree(int n, T initVal, std::function<T(T&, T&)> f) : ARY_SIZE(1), initVal(initVal), merge(f) { init(n); }
 
    inline void update(int i, T val) {
        i += ARY_SIZE;
        ary[i] = val;
        while (i > 1) {
            i >>= 1;
            ary[i] = merge(ary[i << 1], ary[(i << 1) + 1]);
        }
    }

    inline void add(int i, T val) {
        update(i, ary[i + ARY_SIZE] + val);
    }

    inline T query(int l, int r) {
        if (l >= r) return initVal;
        T vl = initVal, vr = initVal;
        for (l += ARY_SIZE, r += ARY_SIZE; l != r; l >>= 1, r >>= 1) {
            if (l & 1) vl = merge(vl, ary[l++]);
            if (r & 1) vr = merge(ary[--r], vr);
        }
        return merge(vl, vr);
    }

    T operator[](int i) { return ary[i + ARY_SIZE]; }
 
    void debugShow() {
        for (int i = ARY_SIZE; i < ARY_SIZE << 1; ++i) std::cerr << ary[i] << " ";
        std::cerr << "\n";
    }
};

const int MAX = 2e5+10;

int N, Q, A[MAX], X[MAX], Y[MAX];
bool C[MAX];

vi solve() {
    SegmentTree<int> cnt(N+10, SUM);
    vi b(N);
    REPR (q, Q) {
        if (C[q]) {
            b[X[q]] += 1ll * cnt.query(0, X[q]+1) * Y[q];
        } else {
            cnt.add(X[q], 1);
            cnt.add(Y[q]+1, -1);
        }
    }
    REP (i, N) {
        b[i] += 1ll * cnt.query(0, i+1) * A[i];
    }
    return b;
}

int main() {
    cin >> N >> Q;
    REP (i, N) cin >> A[i];
    REP (q, Q) {
        char c;
        cin >> c >> X[q] >> Y[q];
        C[q] = (c == 'A');
        X[q]--;
        if (!C[q]) Y[q]--;
    }
    vi ans = solve();
    REP (i, N) {
        cout << ans[i];
        cout << (i==N-1 ? '\n' : ' ');
    }
}
0