結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー parukiparuki
提出日時 2016-07-29 15:49:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,236 bytes
コンパイル時間 2,627 ms
コンパイル使用メモリ 193,068 KB
実行使用メモリ 259,392 KB
最終ジャッジ日時 2024-11-06 18:24:55
合計ジャッジ時間 25,688 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;

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;

        value = lazyValue = vll(vectorSize);
        lazyClear = vi(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;
    X = L = R = vll(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);
    }
    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