結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー pekempey
提出日時 2016-11-17 16:06:38
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 41 ms / 5,000 ms
コード長 2,131 bytes
コンパイル時間 2,694 ms
コンパイル使用メモリ 180,124 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2024-11-26 03:01:44
合計ジャッジ時間 4,733 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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 fix(int k) {
    for (int i = 0; i < 2; i++) {
        seg[k].cnt[i] = seg[k * 2].cnt[i] + seg[k * 2 + 1].cnt[i];
    }
}

void upd(int l, int r, int v) {
    l += N; r += N;
    for (int i = 17; i >= 1; i--) push(l >> i, 1 << i), push(r >> i, 1 << i);
    int ll = l / (l & -l);
    int rr = r / (r & -r) - 1;
    int s = 1;
    for (; l < r; l >>= 1, r >>= 1, s <<= 1) {
        if (l & 1) set_lazy(l++, v, s);
        if (r & 1) set_lazy(--r, v, s);
    }
    while (ll > 1) fix(ll >>= 1);
    while (rr > 1) fix(rr >>= 1);
}

int result[2];

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

void query(int l, int r) {
    l += N; r += N;
    for (int i = 17; i >= 1; i--) push(l >> i, 1 << i), push(r >> i, 1 << i);
    result[0] = result[1] = 0;
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) app(l++);
        if (r & 1) app(--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) {
            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