結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー pekempeypekempey
提出日時 2015-07-25 17:43:17
言語 C++11
(gcc 11.4.0)
結果
RE  
実行時間 -
コード長 3,571 bytes
コンパイル時間 1,935 ms
コンパイル使用メモリ 167,504 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-17 13:21:05
合計ジャッジ時間 5,711 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a) for (int i = 0; i < (a); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) for (int i = (a) - 1; i >= 0; i--)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define itall(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
const ll inf = 1e9;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
const double eps = 1e-8;
template<typename T> inline T sq(T a) { return a * a; }
template<typename T> inline T cb(T a) { return a * a * a; }
template<typename T> inline bool umin(T &a, const T &b) { return b < a && (a = b, true); }
template<typename T> inline bool umax(T &a, const T &b) { return a < b && (a = b, true); }

int N, Q;
ll x[150000], l[150000], r[150000];
ll w[300000];

ll sumseg[300000][6], lazy[300000];
ll bit[300002];
int size;

void add(ll k, ll x) {
    while (k <= size) {
        bit[k] += x;
        k += k & -k;
    }
}

ll sum(ll k) {
    ll res = 0;
    while (k) {
        res += bit[k];
        k -= k & -k;
    }
    return res;
}

void init(int n) {
    size = 1;
    while (size < n) size *= 2;
}

void eval_lazy(int k, int l, int r) {
    if (lazy[k] == 0) return;

    rep2 (i, 1, 6) {
        if (i == lazy[k]) {
            sumseg[k][i] += sum(r) - sum(l);
        } else {
            sumseg[k][i] = 0;
        }
    }

    if (k < size) {
        lazy[k * 2 + 1] = lazy[k];
        lazy[k * 2 + 2] = lazy[k];
    }
    lazy[k] = 0;
}

void update(int k) {
    rep (i, 6) {
        sumseg[k][i] = sumseg[k * 2 + 1][i] + sumseg[k * 2 + 2][i];
    }
}

void update(int a, int b, int x, int k = 0, int l = 0, int r = size) {
    eval_lazy(k, l, r);

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

    if (a <= l && r <= b) {
        lazy[k] = x;
        eval_lazy(k, l, r);
    } else {
        update(a, b, x, k * 2 + 1, l, (l + r) / 2);
        update(a, b, x, k * 2 + 2, (l + r) / 2, r);
        update(k);
    }
}

void query(int res[], int a, int b, int k = 0, int l = 0, int r = size) {
    eval_lazy(k, l, r);

    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
        rep (i, 6) res[i] += sumseg[k][i];
        return;
    }

    query(res, a, b, k * 2 + 1, l, (l + r) / 2);
    query(res, a, b, k * 2 + 2, (l + r) / 2, r);

    update(k);
}

int main() {
    cin >> N >> Q;
    rep (i, Q) cin >> x[i] >> l[i] >> r[i];

    vector<ll> xs;

    rep (i, Q) {
        xs.push_back(l[i]);
        xs.push_back(r[i]);
    }

    sort(itall(xs));
    xs.erase(unique(itall(xs)), xs.end());

    xs.push_back(xs[xs.size() - 1] + 1);

    rep (i, Q) {
        l[i] = lower_bound(itall(xs), l[i]) - xs.begin();
        r[i] = lower_bound(itall(xs), r[i]) - xs.begin();

        w[l[i]] = xs[l[i] + 1] - xs[l[i]];
        w[r[i]] = xs[r[i] + 1] - xs[r[i]];
    }

    init(xs.size() + 1);

    rep (i, xs.size()) {
        add(i + 1, w[i]);
    }

    int ans[6] = {};

    rep (i, Q) {
        int q[6] = {};

        if (x[i] == 0) {
            query(q, l[i], r[i] + 1);

            int maxv = -1, maxi = 0;
            rep2 (i, 1, 6) {
                if (q[i] > maxv) {
                    maxv = q[i];
                    maxi = i;
                } else if (q[i] == maxv) {
                    maxi = -1;
                    break;
                }
            }

            if (maxi <= 0) continue;

            ans[maxi] += maxv;
        } else {
            update(l[i], r[i] + 1, x[i]);
        }
    }

    query(ans, 0, size);

    rep (i, 5) {
        if (i > 0) cout << " ";
        cout << ans[i + 1];
    }
    cout << endl;
}
0