結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー mayoko_
提出日時 2015-07-20 22:09:19
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 87 ms / 5,000 ms
コード長 2,594 bytes
コンパイル時間 1,073 ms
コンパイル使用メモリ 95,044 KB
実行使用メモリ 7,296 KB
最終ジャッジ日時 2024-07-08 11:25:50
合計ジャッジ時間 3,538 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
#include<complex>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef complex<double> C;

enum class color {mine, yours, invalid};
const int MAXN = (1<<17);

struct SegTreeLazy {
    vector<int> val;
    vector<color> lazy;

    SegTreeLazy() {val.resize(2*MAXN); lazy.resize(2*MAXN, color::invalid);}

    int get(int x, int y, int l = 0, int r = MAXN, int k = 1) {
        if (r <= x || y <= l) return 0;
        if (x <= l && r <= y) return val[k];
        x = max(x, l); y = min(y, r);
        if (lazy[k] != color::invalid) {
            if (lazy[k] == color::mine) return y-x;
            else return 0;
        }
        return get(x, y, l, (l+r)/2, 2*k) + get(x, y, (l+r)/2, r, 2*k+1);
    }

    void update(int x, int y, color col, int l = 0, int r = MAXN, int k = 1) {
        if (l >= r) return;
        if (x <= l && r <= y) {
            lazy[k] = col;
            val[k] = lazy[k] != color::yours ? (r-l) : 0;
        } else if (l < y && x < r) {
            if (lazy[k] != color::invalid) {
                lazy[k*2] = lazy[k*2+1] = lazy[k];
                val[k*2] = val[k*2+1] = lazy[k] != color::yours ? (r-l)/2 : 0;
                lazy[k] = color::invalid;
            }
            update(x, y, col, l, (l+r)/2, k*2);
            update(x, y, col, (l+r)/2, r, k*2+1);
            val[k] = val[k*2] + val[k*2+1];
        }
    }
};

SegTreeLazy seg[2];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, Q;
    cin >> N;
    cin >> Q;
    ll A = 0, B = 0;
    while (Q--) {
        int x, l, r;
        cin >> x >> l >> r;
        if (x == 0) {
            int a = seg[0].get(l, r+1);
            int b = seg[1].get(l, r+1);
            if (a < b) B += b;
            else if (a > b) A += a;
        } else if (x == 1) {
            seg[0].update(l, r+1, color::mine);
            seg[1].update(l, r+1, color::yours);
        } else {
            seg[1].update(l, r+1, color::mine);
            seg[0].update(l, r+1, color::yours);
        }
    }
    A += seg[0].get(0, N+1);
    B += seg[1].get(0, N+1);
    cout << A << " " << B << endl;
    return 0;
}
0