結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー はまやんはまやん
提出日時 2017-04-10 14:20:23
言語 C++14
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 69 ms / 5,000 ms
コード長 3,336 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,677 ms
コンパイル使用メモリ 173,364 KB
実行使用メモリ 11,664 KB
最終ジャッジ日時 2024-07-18 05:40:18
合計ジャッジ時間 3,405 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)




int N, Q;
//-----------------------------------------------------------------------------------
typedef long long ll;
struct LazySeg_sum {

    struct Data {
        ll val;
        ll add;
        ll sum;
        bool valset;

        ll calc_sum(int l, int r) {
            if (valset) {
                return (val + add) * (r - l + 1);
            }
            else {
                return sum + add * (r - l + 1);
            }
        }

        void set_data(int x, int y) {
            val = x;
            add = 0;
            valset = true;
        }

        Data() :val(0), add(0), sum(0), valset(false) {}

    };

    vector<Data> data;
    int seg_size;

    LazySeg_sum(int n) {
        for (seg_size = 1; seg_size < n; seg_size *= 2);
        data.assign(seg_size * 2, Data());
    }

    ll set(int a, int b, ll x, int l = 0, int r = -1, int k = 0) {
        if (r == -1) r = seg_size - 1;

        if (a <= l && r <= b) {
            data[k].set_data(x, 0);
            return data[k].calc_sum(l, r);
        }

        if (r < a || b < l) return data[k].calc_sum(l, r);

        if (data[k].valset) {
            data[k * 2 + 1].set_data(data[k].val, data[k].add);
            data[k * 2 + 2].set_data(data[k].val, data[k].add);
        }

        data[k].add = 0;

        data[k].valset = false;

        data[k].sum = set(a, b, x, l, (l + r) / 2, k * 2 + 1) + set(a, b, x, (l + r) / 2 + 1, r, k * 2 + 2);

        return data[k].calc_sum(l, r);
    }

    ll add(int a, int b, ll x, int l = 0, int r = -1, int k = 0) {
        if (r == -1) r = seg_size - 1;

        if (a <= l && r <= b) {
            data[k].add += x;
            return data[k].calc_sum(l, r);
        }

        if (r < a || b < l) return 0;

        if (data[k].valset) {
            data[k * 2 + 1].set_data(data[k].val, 0);
            data[k * 2 + 2].set_data(data[k].val, 0);

            data[k].valset = false;
        }

        data[k].sum = add(a, b, x, l, (l + r) / 2, k * 2 + 1) + add(a, b, x, (l + r) / 2 + 1, r, k * 2 + 2);

        return data[k].calc_sum(l, r);
    }

    ll query(int a, int b, int l = 0, int r = -1, int k = 0) {
        if (r == -1) r = seg_size - 1;

        if (r < a || b < l) return 0;

        if ((a <= l && r <= b) || data[k].valset) {
            return data[k].calc_sum(max(a, l), min(b, r));
        }

        return query(a, b, l, (l + r) / 2, k * 2 + 1) + query(a, b, (l + r) / 2 + 1, r, k * 2 + 2) +
            data[k].add * (min(b, r) - max(a, l) + 1);
    }

};
//-----------------------------------------------------------------------------------
ll e = 1000000;
int main() {
    cin >> N >> Q;

    LazySeg_sum st(N);

    ll A = 0, B = 0;
    rep(q, 0, Q) {
        int x, l, r; scanf("%d%d%d", &x, &l, &r);

        if (x == 0) {
            ll sm = st.query(l, r);

            ll a = sm % e;
            ll b = sm / e;
            if (a < b) B += b;
            else if (a > b) A += a;
        }
        else if (x == 1) st.set(l, r, 1);
        else st.set(l, r, e);
    }

    //rep(i, 0, N) printf("[%lld]\n", st.query(i, i + 1));

    ll sm = st.query(0, N - 1);
    //cout << sm << endl;

    ll a = sm % e;
    ll b = sm / e;

    A += a;
    B += b;

    printf("%lld %lld\n", A, B);
}
0