QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#463389 | #8340. 3 Sum | PlentyOfPenalty | RE | 0ms | 0kb | C++20 | 4.0kb | 2024-07-04 19:41:52 | 2024-07-04 19:41:53 |
Judging History
answer
#include <bits/stdc++.h>
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define log(...) (void(0))
#define endl '\n'
#endif
using namespace std;
using ull = unsigned long long;
#define at(x, i) (((x) >> (i)) & 1)
const int N = 2e4 + 9;
int n, q, c;
ull b[N];
inline void output(ull x) {
for (unsigned int i = 0; i < 64; i++) {
log("%d", (int)at(x, i));
}
log("\n");
}
struct matrix {
ull a[64], b[64];
void clear() {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
}
void output() {
assert(self_check());
for (unsigned int i = 0; i < 64; i++) {
for (unsigned int j = 0; j < 64; j++) {
log("%d", (int)at(a[j], i));
}
log("\n");
}
}
bool self_check() {
for (unsigned int i = 0; i < 64; i++)
for (unsigned int j = 0; j < 64; j++)
if (at(a[i], j) != at(b[j], i)) {
return false;
}
return true;
}
void set(int i, int j) { // i?j?
a[j] |= 1ull << i;
b[i] |= 1ull << j;
}
matrix operator+(matrix rhs) const {
for (unsigned int i = 0; i < 64; i++) {
rhs.a[i] ^= a[i];
rhs.b[i] ^= b[i];
}
return rhs;
}
matrix operator*(const matrix &rhs) const {
static matrix c;
c.clear();
for (int i = 0; i < 64; ++i) {
for (int j = 0; j < 64; ++j) {
ull fl = __builtin_popcount(b[i] & rhs.a[j]) & 1;
c.a[j] |= (fl << i);
c.b[i] |= (fl << j);
}
}
return c;
}
} op[N];
matrix from_vec(ull v) {
static matrix c;
c.clear();
c.a[0] = v;
for (unsigned int i = 0; i < 64; i++) {
c.b[i] = (v >> i) & 1;
}
return c;
}
struct atom {
matrix x, c;
};
inline atom merge(const atom &l, const atom &r) { return atom{r.x * l.x, r.c + r.x * l.c}; }
struct segment {
int l, r, mid;
atom dat;
} p[N << 2];
void build(int u, int l, int r) {
p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
if (l == r) {
p[u].dat = {op[l], from_vec(b[l])};
// log("c[%d:%d]: ", p[u].l, p[u].r), output(p[u].dat.c.a[0]);
return;
}
build(u << 1, l, p[u].mid);
build(u << 1 | 1, p[u].mid + 1, r);
p[u].dat = merge(p[u << 1].dat, p[u << 1 | 1].dat);
// log("c[%d:%d]: ", p[u].l, p[u].r), output(p[u].dat.c.a[0]);
}
void modify(int u, int k) {
if (p[u].l == p[u].r) {
p[u].dat = {op[k], from_vec(b[k])};
return;
}
if (k <= p[u].mid) {
modify(u << 1, k);
} else {
modify(u << 1 | 1, k);
}
p[u].dat = merge(p[u << 1].dat, p[u << 1 | 1].dat);
}
atom query(int u, int l, int r) {
// log("query %d %d %d\n", u, l, r);
if (p[u].l == l && p[u].r == r) {
return p[u].dat;
}
if (r <= p[u].mid) return query(u << 1, l, r);
if (l > p[u].mid) return query(u << 1 | 1, l, r);
return merge(query(u << 1, l, p[u].mid), query(u << 1 | 1, p[u].mid + 1, r));
}
void read_oper(matrix &op, ull &b) {
op.clear();
int m;
cin >> m;
vector<int> s(m), o(m);
vector<ull> a(m);
for (int i = 0; i < m; i++) {
cin >> s[i] >> o[i] >> a[i];
// log(">> %d %d %llu\n", s[i], o[i], a[i]);
}
cin >> b;
for (int i = 0; i < m; i++) {
if (o[i] == 0) {
for (int j = 0; j < 64; j++) {
if (at(a[i], j)) {
b ^= 1ull << j;
}
a[i] ^= 1ull << j;
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < 64; j++)
if (at(a[i], j)) {
op.set(j, (j - s[i] + 64) % 64);
}
}
}
int main() {
#ifdef memset0
freopen("H.in", "r", stdin);
#endif
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q >> c;
for (int i = 1; i <= n; i++) {
read_oper(op[i], b[i]);
}
build(1, 1, n);
for (int o, k, l, r, i = 1; i <= q; i++) {
cin >> o;
if (o == 0) {
ull x;
cin >> l >> r >> x;
atom res = query(1, l, r);
matrix s = res.c + res.x * from_vec(x);
// res.x.output();
cout << s.a[0] << endl;
// log("x: "), output(x);
// log("s: "), output(s.a[0]);
// log("c: "), output(res.c.a[0]);
// log("t: "), output((res.x * from_vec(x)).a[0]);
} else {
cin >> k;
read_oper(op[k], b[k]);
modify(1, k);
}
}
}
詳細信息
Test #1:
score: 0
Runtime Error
input:
4 1 0 1 10 17