結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー pekempey
提出日時 2016-11-17 18:37:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 5,000 ms
コード長 4,157 bytes
コンパイル時間 2,510 ms
コンパイル使用メモリ 189,312 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-26 03:05:28
合計ジャッジ時間 3,452 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;

double elapsed() {
    static clock_t curr;
    clock_t prev = curr;
    curr = clock();
    return (double)(curr - prev) / CLOCKS_PER_SEC;
}

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;
}

template<int N>
struct Bitset {
    uint64_t a[N / 64] = {};
    int cache = 0;

    void set() {
        cache = N;
        for (int i = 0; i < N / 64; i++) a[i] = UINT64_MAX;
    }

    void set(int l, int r) {
        cache = -1;
        if (l / 64 == r / 64 && r % 64 != 0) {
            a[l / 64] |= UINT64_MAX >> (64 - r + l) << l;
            return;
        }
        if (l % 64 != 0) a[l / 64] |= ~((1ULL << (l % 64)) - 1);
        if (r % 64 != 0) a[r / 64] |= (1ULL << (r % 64)) - 1;
        l = (l + 63) / 64;
        r = r / 64;
        for (; l < r; l++) a[l] = UINT64_MAX;
    }

    void unset() {
        cache = 0;
        for (int i = 0; i < N / 64; i++) a[i] = 0;
    }

    void unset(int l, int r) {
        cache = -1;
        if (l / 64 == r / 64 && r % 64 != 0) {
            a[l / 64] &= ~(UINT64_MAX >> (64 - r + l) << l);
            return;
        }
        if (l % 64 != 0) a[l / 64] &= (1ULL << (l % 64)) - 1;
        if (r % 64 != 0) a[r / 64] &= ~((1ULL << (r % 64)) - 1);
        l = (l + 63) / 64;
        r = r / 64;
        for (; l < r; l++) a[l] = 0;
    }

    int count() {
        if (cache != -1) return cache;
        int res = 0;
        for (int i = 0; i < N / 64; i++) {
            res += __builtin_popcountll(a[i]);
        }
        return cache = res;
    }

    int count(int l, int r) {
        if (l / 64 == r / 64 && r % 64 != 0) {
            return __builtin_popcountll(a[l / 64] & (UINT64_MAX >> (64 - r + l) << l));
        }
        int res = 0;
        if (l % 64 != 0) res += __builtin_popcountll(a[l / 64] & (~((1ULL << (l % 64)) - 1)));
        if (r % 64 != 0) res += __builtin_popcountll(a[r / 64] & ((1ULL << (r % 64)) - 1));
        l = (l + 63) / 64;
        r = r / 64;
        for (; l < r; l++) res += __builtin_popcountll(a[l]);
        return res;
    }
};
const int M = 1 << 17;
const int S = 1 << 10;
Bitset<S> A[M / S][2];
char lz[M / S];

void push(int k) {
    if (lz[k] == -1) return;
    A[k][lz[k] ^ 0].set();
    A[k][lz[k] ^ 1].unset();
    lz[k] = -1;
}

void fill(int k, int v, int l, int r) {
    A[k][v ^ 0].set(l, r);
    A[k][v ^ 1].unset(l, r);
}

void upd(int l, int r, int v) {
    if (l == r) return;
    push(l / S);
    push(r / S);
    if (l / S == r / S) return fill(l / S, v, l % S, (r - 1) % S + 1);
    if (l % S != 0) fill(l / S, v, l % S, S);
    if (r % S != 0) fill(r / S, v, 0, r % S);
    l = (l + S - 1) / S;
    r = r / S;
    for (; l < r; l++) lz[l] = v;
}

int result[2];

void query(int l, int r) {
    if (l == r) return;
    result[0] = result[1] = 0;
    push(l / S);
    push(r / S);
    if (l / S == r / S) {
        for (int i = 0; i < 2; i++) {
            result[i] = A[l / S][i].count(l % S, (r - 1) % S + 1);
        }
        return;
    }
    if (l % S != 0) for (int i = 0; i < 2; i++) result[i] += A[l / S][i].count(l % S, S);
    if (r % S != 0) for (int i = 0; i < 2; i++) result[i] += A[r / S][i].count(0, r % S);
    l = (l + S - 1) / S;
    r = r / S;
    for (; l < r; l++) {
        if (lz[l] == -1) {
            result[0] += A[l][0].count();
            result[1] += A[l][1].count();
        } else {
            result[lz[l]] += S;
        }
    }
}

int main() {
    elapsed();
    memset(lz, -1, sizeof(lz));
    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];
            if (result[0] < result[1]) b += result[1];
        } else upd(l, r, x);
    }
    query(0, M - 1);
    a += result[0];
    b += result[1];
    cout << a << " " << b << endl;
    cerr << elapsed() << endl;
}
0