結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー |
|
提出日時 | 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 |
ソースコード
#pragma GCC optimize ("O3")#pragma GCC target ("avx")#include <bits/stdc++.h>#define getchar getchar_unlockedusing 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;}