QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#463391 | #8335. Fast Hash Transform | PlentyOfPenalty | WA | 2ms | 7764kb | C++20 | 4.1kb | 2024-07-04 19:44:12 | 2024-07-04 19:44:12 |
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() const {
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];
}
assert(rhs.self_check());
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);
}
}
assert(c.self_check());
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);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7764kb
input:
3 5 1 1 4 0 0 51966 1 60 0 0 0 1 0 0 16 15 0 1 1 771 0 2 2 32368 0 3 3 0 1 2 2 0 0 15 61 1 4095 46681 0 1 3 2023
output:
64206 2023 31 1112
result:
ok 4 tokens
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 5752kb
input:
9 9 3 32 9 0 17785061119123981789 33 0 10890571864137198682 42 0 9437574736788763477 34 0 5239651887868507470 55 0 14741743279679654187 27 1 1444116632918569317 38 1 5740886562180922636 1 1 8113356142324084796 3 0 10955266306442425904 60 0 16421026339459788005 53 0 1595107134632608917 48 1 923204972...
output:
10735028597927780461 6286254107986266013 2891025415212112008 5292801977632587806 16546994779959756186 17580801933839203485
result:
wrong answer 1st words differ - expected: '9487331362121050549', found: '10735028597927780461'