結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー paruki
提出日時 2016-08-12 03:49:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 260 ms / 5,000 ms
コード長 4,141 bytes
コンパイル時間 1,864 ms
コンパイル使用メモリ 179,680 KB
実行使用メモリ 7,808 KB
最終ジャッジ日時 2024-11-07 11:56:04
合計ジャッジ時間 4,321 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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;

struct LazySegTree{
    int dataSize;
    vi val;
    vector<bool> lazyZero, lazyOne;

    LazySegTree(int n){
        dataSize = 1;
        while(dataSize < n)dataSize *= 2;
        int treeSize = 2 * dataSize - 1;
    
        val = vi(treeSize);
        lazyZero = lazyOne = vector<bool>(treeSize);
    }

    void propagate(int index, int curL, int curR){
        // 自分の値をlazyにもとづいて書き換えて自分のlazyをクリア。
        // 子のlazyを書き換える。
        if(lazyZero[index]){
            val[index] = 0;
        }
        
        if(lazyOne[index])val[index] = curR-curL;
        
        if(curR - curL > 1){
            int l = index * 2 + 1, r = index * 2 + 2;
            if(lazyZero[index]){
                lazyOne[l] = lazyOne[r] = false;
                lazyZero[l] = lazyZero[r] = true;
            } else if(lazyOne[index]){
                lazyOne[l] = lazyOne[r] = true;
                lazyZero[l] = lazyZero[r] = false;
            }
        }

        lazyZero[index] = lazyOne[index] = false;
    }

    // [curL, curR) を評価する
    void update(int index, int curL, int curR, int givenL, int givenR, bool isAdd){
        // 範囲外であろうとpropagateは必ず呼ぶ。そうでないと、親がうまく評価されない
        propagate(index, curL, curR);

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

        // 範囲内
        if(givenL <= curL && curR <= givenR){
            // 直接書き換えないでindexのlazyを書き換えてpropagateを呼ぶ
            if(!isAdd){
                lazyZero[index] = true;
                lazyOne[index] = false;
            }
            else{
                lazyOne[index] = true;
                lazyZero[index] = false;
            }
            propagate(index, curL, curR);
        } else{ // 範囲外と範囲内が含まれる(長さ2以上)
            int mid = (curL + curR) / 2;
            update(index * 2 + 1, curL, mid, givenL, givenR, isAdd);
            update(index * 2 + 2, mid, curR, givenL, givenR, isAdd);
            val[index] = val[index * 2 + 1] + val[index * 2 + 2];
        }
    }

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

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

    int 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 val[index];
        } else{
            int mid = (curL + curR) / 2;
            int res1 = query(index * 2 + 1, curL, mid, givenL, givenR);
            int res2 = query(index * 2 + 2, mid, curR, givenL, givenR);
            return res1 + res2;
        }
    }
};

const int MAX = (int)1e5 + 1;
int N, Q, X[MAX], L[MAX], R[MAX];

void solve(){
    vll ans(2);
    vector<LazySegTree> segTree(2, LazySegTree(N));

    rep(i, Q){
        R[i]++;
        X[i]--;
        if(X[i] == -1){
            vll val(2);
            rep(j, 2)val[j] = segTree[j].query(L[i], R[i]);
            if(val[0] > val[1])ans[0] += val[0];
            else if(val[1] > val[0])ans[1] += val[1];
        } else{
            segTree[X[i]].update(L[i], R[i], true);
            segTree[1-X[i]].update(L[i], R[i], false);
        }
    }
    
    rep(i, 2)ans[i] += segTree[i].query(0, N);

    cout << ans[0] << ' ' << ans[1] << endl;
}

int main(){
    while(cin >> N >> Q){
        rep(i, Q)scanf("%d%d%d", &X[i], &L[i], &R[i]);
        solve();
    }
}
0