結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0