結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー pekempey
提出日時 2016-11-17 16:16:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 62 ms / 5,000 ms
コード長 2,024 bytes
コンパイル時間 2,773 ms
コンパイル使用メモリ 180,916 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-11-26 03:02:06
合計ジャッジ時間 4,062 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include <bits/stdc++.h>
#define getchar getchar_unlocked
using namespace std;

int in() {
    int64_t n;
    int c;
    while ((c = getchar()) < '0') if (c == EOF) return -1;
    n = c - '0';
    while ((c = getchar()) >= '0') n = n * 10 + c - '0';
    return n;
}

const int N = 1 << 17;

struct node {
    int cnt[2];
    int lz = -1;
};
node seg[N * 2];

void set_lazy(int k, int v, int s) {
    if (v == 0) {
        seg[k].cnt[0] = s;
        seg[k].cnt[1] = 0;
    } else {
        seg[k].cnt[0] = 0;
        seg[k].cnt[1] = s;
    }
    seg[k].lz = v;
}

void push(int k, int s) {
    if (seg[k].lz == -1) return;
    if (k < N) {
        set_lazy(k * 2 + 0, seg[k].lz, s / 2);
        set_lazy(k * 2 + 1, seg[k].lz, s / 2);
    }
    seg[k].lz = -1;
}

void upd(int a, int b, int v, int k = 1, int l = 0, int r = N) {
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
        set_lazy(k, v, r - l);
        return;
    }
    push(k, r - l);
    upd(a, b, v, k * 2 + 0, l, (l + r) / 2);
    upd(a, b, v, k * 2 + 1, (l + r) / 2, r);
    for (int i = 0; i < 2; i++) {
        seg[k].cnt[i] = seg[k * 2 + 0].cnt[i] + seg[k * 2 + 1].cnt[i];
    }
}

int result[2];

void app(int k) {
    result[0] += seg[k].cnt[0];
    result[1] += seg[k].cnt[1];
}

void query(int a, int b, int k = 1, int l = 0, int r = N) {
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) return app(k);
    push(k, r - l);
    query(a, b, k * 2 + 0, l, (l + r) / 2);
    query(a, b, k * 2 + 1, (l + r) / 2, r);
}

int main() {
    int n = in(), q = in();
    int64_t a = 0, b = 0;
    while (q--) {
        int x = in() - 1, l = in(), r = in() + 1;
        if (x == -1) {
            result[0] = result[1] = 0;
            query(l, r);
            if (result[0] > result[1]) a += result[0];
            else if (result[0] < result[1]) b += result[1];
        } else upd(l, r, x);
    }
    a += seg[1].cnt[0];
    b += seg[1].cnt[1];
    cout << a << " " << b << endl;
}
0