結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
コンテスト
ユーザー paruki
提出日時 2019-08-06 16:02:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,416 bytes
コンパイル時間 2,202 ms
コンパイル使用メモリ 193,652 KB
実行使用メモリ 257,492 KB
最終ジャッジ日時 2024-07-18 14:04:19
合計ジャッジ時間 22,995 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 MLE * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

template<class T>
void resize(vector<T> &a, int n) {
    a.reserve(n);
    a.resize(n);
}

ll N;
int Q, M;
vll lrVal, X, L, R;
const int nTeam = 5;
const ll MOD = (ll)1e18 + 9;

// 1.5*10^5 * 10^13 = 1.5*10^18 < LLNG_MAX/2 なので
// SegTreeの中ではオーバーフローしない。bonusを得た場合だけ加算の時に気をつければ良い。
class SegTreeLazy {
public:
    int dataSize;
    vll value, lazyValue;
    vi lazyClear;
    SegTreeLazy(int n) {
        dataSize = 1;
        while (dataSize < n)dataSize *= 2;
        int vectorSize = 2 * dataSize - 1;

        resize(value, vectorSize);
        resize(lazyValue, vectorSize);
        resize(lazyClear, vectorSize);
    }

    void propagate(int index, int curL, int curR) {
        if (lazyClear[index])value[index] = 0;
        // dataSizeは2^k >= M を満たす最小の2^kであるから、
        // 2^k > M かもしれない。
        // よって、lrValの範囲外参照に注意
        value[index] += lazyValue[index] * (lrVal[min(M - 1, curR)] - lrVal[min(M - 1, curL)]);

        if (curR - curL > 1) {
            int indexL = index * 2 + 1, indexR = index * 2 + 2;

            if (lazyClear[index])
                lazyValue[indexL] = lazyValue[indexR] = 0;

            for (int indexC : {indexL, indexR}) {
                lazyClear[indexC] |= lazyClear[index];
                lazyValue[indexC] += lazyValue[index];
            }
        }

        lazyValue[index] = lazyClear[index] = 0;
    }

    // [curL, curR) を評価する
    void update(int index, int curL, int curR, int givenL, int givenR, int isAdd) {
        // 評価し終わったら、必ずlazyClear[index]とlazyValue[index]はデフォルト値になっているはず
        // 範囲外であろうとpropagateは必ず呼ぶ。
        propagate(index, curL, curR);

        // 範囲外
        if (curR <= givenL || givenR <= curL)return;

        if (givenL <= curL && curR <= givenR) {
            // 直接書き換えないで、lazyClear,lazyValueを更新してからpropagateを呼ぶ
            if (isAdd) {
                lazyValue[index]++;
            } else {
                lazyClear[index] = 1;
                lazyValue[index] = 0;
            }
            propagate(index, curL, curR);
        } else {
            int mid = (curL + curR) / 2;
            update(index * 2 + 1, curL, mid, givenL, givenR, isAdd);
            update(index * 2 + 2, mid, curR, givenL, givenR, isAdd);

            value[index] = value[index * 2 + 1] + value[index * 2 + 2];
        }
    }

    void update(int l, int r, int isAdd) {
        update(0, 0, dataSize, l, r, isAdd);
    }

    ll query(int l, int r) {
        return query(0, 0, dataSize, l, r);
    }

    ll query(int index, int curL, int curR, int givenL, int givenR) {
        // 範囲外
        if (curR <= givenL || givenR <= curL)return 0;

        propagate(index, curL, curR);

        if (givenL <= curL && curR <= givenR) {
            return value[index];
        } else {
            int mid = (curL + curR) / 2;
            ll resL = query(index * 2 + 1, curL, mid, givenL, givenR);
            ll resR = query(index * 2 + 2, mid, curR, givenL, givenR);
            return resL + resR;
        }
    }
};

int main() {
    cin >> N >> Q;

    resize(X, Q);
    resize(L, Q);
    resize(R, Q);

    // 区間の座標圧縮
    rep(i, Q) {
        scanf("%lld%lld%lld", &X[i], &L[i], &R[i]);
        for (ll val : {L[i], L[i] + 1, R[i], R[i] + 1})
            lrVal.push_back(val);
    }
    lrVal.shrink_to_fit();
    sort(all(lrVal));
    lrVal.erase(unique(all(lrVal)), lrVal.end());
    rep(i, Q) {
        L[i] = (int)(lower_bound(all(lrVal), L[i]) - lrVal.begin());
        R[i] = (int)(lower_bound(all(lrVal), R[i]) - lrVal.begin());
    }

    M = sz(lrVal);

    vector<SegTreeLazy> segTree(nTeam, SegTreeLazy(M));

    vll ans(nTeam);

    rep(q, Q) {
        int x = (int)X[q], l = (int)L[q], r = (int)R[q];
        // チームのインデックスを0-Originにしておく
        --x;
        // [l,r] => [l, r)
        r++;

        if (x == -1) {
            vector<pair<ll, int>> bonusAndTeam(nTeam);
            rep(i, nTeam) {
                bonusAndTeam[i] = mp(segTree[i].query(l, r), i);
            }
            sort(bonusAndTeam.rbegin(), bonusAndTeam.rend());
            ll bonus = bonusAndTeam[0].first;
            // トップタイがいたら、ボーナス無し
            if (bonus != bonusAndTeam[1].first) {
                (ans[bonusAndTeam[0].second] += bonus) %= MOD;
            }
        } else {
            rep(i, nTeam) {
                if (i == x)segTree[i].update(l, r, 1);
                else segTree[i].update(l, r, 0);
            }
        }
    }

    rep(i, nTeam) {
        (ans[i] += segTree[i].query(0, M)) %= MOD;
        printf("%lld%c", ans[i], i != nTeam - 1 ? ' ' : '\n');
    }
}
0