QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662065 | #8335. Fast Hash Transform | rizynvu | WA | 4ms | 44556kb | C++14 | 2.4kb | 2024-10-20 20:25:41 | 2024-10-20 20:25:53 |
Judging History
answer
#include<bits/stdc++.h>
#define gc getchar_unlocked
template<typename Ty>
inline Ty read() {
Ty x = 0; int c = gc(); bool f = false;
while (! isdigit(c)) f |= c == '-', c = gc();
while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
return f ? -x : x;
}
using ull = unsigned long long;
inline ull shift(ull x, int y) {
if (! y) return x;
return (x << y) | (x >> 64 - y);
}
const int maxn = 2e4 + 10;
int n;
struct node_t {
ull a[64], k;
inline node_t() {
memset(a, 0, sizeof(a)), k = 0;
}
inline void init() {
*this = node_t();
int m = read<int>();
while (m--) {
int x = read<int>(), op = read<int>();
ull val = read<ull>();
if (op == 0) {
k ^= val, val = ~ val;
}
a[x] = val;
}
k ^= read<ull>();
}
inline node_t operator * (const node_t &b) const {
node_t c;
c.k = b.k;
for (int i = 0; i < 64; i++) {
c.k ^= shift(k, i) & a[i];
for (int j = 0; j < 64; j++) {
c.a[(i + j) & 63] ^= shift(a[i], j) & b.a[j];
}
}
return c;
}
inline ull operator () (const ull &x) const {
ull y = k;
for (int i = 0; i < 64; i++) {
y ^= shift(x, i) & a[i];
}
return y;
}
} tr[maxn * 4];
inline void build(int k = 1, int l = 1, int r = n) {
if (l == r) {
return tr[k].init(), void();
}
int mid = l + r >> 1;
build(k << 1, l, mid), build(k << 1 | 1, mid + 1, r);
tr[k] = tr[k << 1] * tr[k << 1 | 1];
}
inline void update(int x, int k = 1, int l = 1, int r = n) {
if (l == r) {
return tr[k].init(), void();
}
int mid = l + r >> 1;
if (x <= mid) update(x, k << 1, l, mid);
else update(x, k << 1 | 1, mid + 1, r);
tr[k] = tr[k << 1] * tr[k << 1 | 1];
}
inline void query(int x, int y, ull &z, int k = 1, int l = 1, int r = n) {
if (l == r) {
return z = tr[k](z), void();
}
int mid = l + r >> 1;
if (x <= mid) query(x, y, z, k << 1, l, mid);
if (y > mid) query(x, y, z, k << 1 | 1, mid + 1, r);
}
int main() {
n = read<int>();
int q = read<int>(), c = read<int>();
build();
while (q--) {
int op = read<int>(), x = read<int>();
if (op == 0) {
int y = read<int>(); ull z = read<int>();
query(x, y, z);
printf("%lld\n", z);
} else {
update(x);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 44556kb
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: 4ms
memory: 44528kb
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:
2251943714755008405 -2901818001849276369 -7002521193019191255 -1822239737557010060 5305861336387510562 -865942139870348131
result:
wrong answer 1st words differ - expected: '9487331362121050549', found: '2251943714755008405'