QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#662071 | #8335. Fast Hash Transform | rizynvu | TL | 1126ms | 44516kb | C++14 | 2.4kb | 2024-10-20 20:31:16 | 2024-10-20 20:31:28 |
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<ull>();
query(x, y, z);
printf("%llu\n", z);
} else {
update(x);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 44516kb
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: 0
Accepted
time: 0ms
memory: 44452kb
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:
9487331362121050549 3906661590723083106 15757672015979182109 4975471776251039345 11503109206538591140 3763610618439604410
result:
ok 6 tokens
Test #3:
score: 0
Accepted
time: 11ms
memory: 44464kb
input:
1 20000 400 32 13 0 1721926083061553294 52 1 8951352260297008058 6 0 3180917732545757991 63 1 14978562500072226750 50 1 7331113732303115313 59 0 688182721924779475 12 0 16291922173168822489 61 0 16018198440613086698 8 0 12494084957448674305 7 0 2834422858291562646 42 1 10354539547309738529 28 0 2541...
output:
11827781865759498816 7454610526276185721 9581050724293785387 2177163806257271094 14004004964877510141 18073834598135159471 16966489063087641088 12289032565388413023 17823140805867698239 18104549908461644670 15570008264282957124 12400954982104000299 9842549278742638708 16535034933613060362 1561642006...
result:
ok 19600 tokens
Test #4:
score: 0
Accepted
time: 154ms
memory: 44464kb
input:
500 20000 400 32 3 0 9869926173615303101 39 1 11114680792832491178 54 1 3380955246053990760 31 0 16868042247314276464 26 0 5814925615581342395 30 1 1114053898154397400 46 1 9215698002668459992 38 1 12938485987410997250 58 0 8030873196223549640 0 0 16055471402053138912 47 1 16568729207788187629 63 0 ...
output:
9119093329811149961 16901643057538871933 17161855998497876349 3964234071281411558 13588188063229334268 15557968976322375381 4612345875926431452 9507168112801039022 9504318642653891468 217407202160767706 12982350345598971306 17957502630817476223 6353877977318728572 15552768639781831485 16778108770682...
result:
ok 19600 tokens
Test #5:
score: 0
Accepted
time: 1126ms
memory: 44444kb
input:
4000 20000 400 35 33 0 18435679328748604368 55 1 10851974578636476759 1 0 11332084644969697080 13 0 4243547822701774011 19 0 18197854269436975495 32 0 10133703694198056054 6 0 12655387670867301210 36 0 1246525872821095171 51 1 812047498663608637 4 0 9797423115860097390 7 1 12105773148377740641 17 0 ...
output:
11875257514484243925 3443357416933857062 16160011677622853538 1582145987019406393 15019762274690743371 3128972641411454448 10632018957963074870 2420532366876270818 16130728863118353230 15834956073901517645 18404809296474853851 10982435108266120760 16463778300806795274 11990886156320593058 1145171640...
result:
ok 19600 tokens
Test #6:
score: -100
Time Limit Exceeded
input:
20000 20000 0 34 47 1 3147866938814566873 50 0 8051884074279018250 4 0 11476150812073861567 54 0 3931985566612211642 60 1 9226417006726638292 49 0 2435425653073267226 33 1 5976119177961927073 40 1 3169532703977184656 2 1 17206894689684881943 37 0 2316971949450684490 7 1 7087775905790436416 18 1 7557...
output:
8031710763259664674 10015579400510819759 9509776159199873854 252965904282343862 17471441301398284397 6167329408972068582 11581702001320217920 13373488743211628824 2094753313448112669 15503010008451014749 384500896248723935 10501371892025480221 8907735695899875922 14479597201387282763 164403466075406...