QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#410393 | #8335. Fast Hash Transform | ucup-team173 | TL | 4863ms | 103840kb | C++20 | 4.4kb | 2024-05-13 22:56:04 | 2024-05-13 22:56:06 |
Judging History
answer
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
struct Matrix {
u64 row[64], col[64];
Matrix() {
memset(row, 0, sizeof(row));
memset(col, 0, sizeof(col));
}
void set(int i, int j, int v) {
if (v) {
row[i] |= 1ULL << j;
col[j] |= 1ULL << i;
} else {
row[i] &= ~(1ULL << j);
col[j] &= ~(1ULL << i);
}
}
} LSHIFT[64];
int dot(u64 a, u64 b) {
return __builtin_popcountll(a & b) & 1;
}
Matrix operator+(Matrix a, Matrix b) {
Matrix c;
for(int i = 0; i < 64; i++) {
c.row[i] = a.row[i] ^ b.row[i];
c.col[i] = a.col[i] ^ b.col[i];
}
return c;
}
Matrix operator*(Matrix a, Matrix b) {
Matrix c;
for(int i = 0; i < 64; i++) {
for(int j = 0; j < 64; j++) {
c.set(i, j, dot(a.row[i], b.col[j]));
}
}
return c;
}
u64 operator*(Matrix a, u64 b) {
u64 c = 0;
for(int i = 0; i < 64; i++) {
if(b >> i & 1) {
c ^= a.col[i];
}
}
return c;
}
struct Info {
Matrix A;
u64 b;
Info() : A(), b(0) {}
Info(Matrix A_, u64 b_) : A(A_), b(b_) {}
};
Info merge(Info a, Info b) {
return {b.A * a.A, b.A * a.b ^ b.b};
}
struct Seg {
int n;
std::vector<Info> seg;
Seg(std::vector<Info> &a) {
n = a.size();
seg.resize(n << 2);
build(a);
}
void build(int o, int l, int r, std::vector<Info> &a) {
if(l == r) {
seg[o] = a[l];
return;
}
int m = (l + r) >> 1;
build(o << 1, l, m, a);
build(o << 1 | 1, m + 1, r, a);
seg[o] = merge(seg[o << 1], seg[o << 1 | 1]);
}
void build(std::vector<Info> &a) {
build(1, 0, n - 1, a);
}
void modify(int o, int l, int r, int p, Info v) {
if(l == r) {
seg[o] = v;
return;
}
int m = (l + r) >> 1;
if(p <= m) {
modify(o << 1, l, m, p, v);
} else {
modify(o << 1 | 1, m + 1, r, p, v);
}
seg[o] = merge(seg[o << 1], seg[o << 1 | 1]);
}
void modify(int p, Info v) {
modify(1, 0, n - 1, p, v);
}
u64 query(int o, int l, int r, int L, int R, u64 b) {
if(L <= l && r <= R) {
return seg[o].A * b ^ seg[o].b;
}
int m = (l + r) >> 1;
if (L <= m) {
b = query(o << 1, l, m, L, R, b);
}
if (R > m) {
b = query(o << 1 | 1, m + 1, r, L, R, b);
}
return b;
}
u64 query(int L, int R, u64 b) {
return query(1, 0, n - 1, L, R, b);
}
};
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0), std::cout.tie(0);
for(int i = 0; i < 64; i++) {
for(int j = 0; j < 64; j++) {
LSHIFT[i].set((i + j) % 64, j, 1);
}
}
auto getInfo = [&]() {
Info res;
int m;
std::cin >> m;
for(int i = 0; i < m; i++) {
u64 s, o, a;
std::cin >> s >> o >> a;
Matrix A = LSHIFT[s];
Matrix B = LSHIFT[0];
if(o == 0) { // or
for(int j = 0; j < 64; j++) {
if(a >> j & 1) {
B.set(j, j, 0);
res.b ^= 1ULL << j;
}
}
} else { // and
for(int j = 0; j < 64; j++) {
if(!(a >> j & 1)) {
B.set(j, j, 0);
}
}
}
res.A = res.A + B * A;
}
u64 b;
std::cin >> b;
res.b ^= b;
return res;
};
int n, q, c;
std::cin >> n >> q >> c;
std::vector<Info> a(n);
for(int i = 0; i < n; i++) {
a[i] = getInfo();
}
Seg seg(a);
for(int i = 0; i < q; i++) {
int op;
std::cin >> op;
if(op == 0) {
u64 l, r, x;
std::cin >> l >> r >> x;
l--, r--;
x = seg.query(l, r, x);
std::cout << x << '\n';
} else {
int p;
std::cin >> p;
p--;
Info v = getInfo();
seg.modify(p, v);
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3812kb
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: 4ms
memory: 3632kb
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: 102ms
memory: 3660kb
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: 333ms
memory: 5760kb
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: 1216ms
memory: 23364kb
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: 0
Accepted
time: 4863ms
memory: 103736kb
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...
result:
ok 20000 tokens
Test #7:
score: 0
Accepted
time: 4853ms
memory: 103840kb
input:
20000 20000 20 28 31 1 17220760822712602145 12 1 10079395927654210001 40 0 10440736241216457314 20 1 14759495678166748212 55 1 8734257463550073646 60 0 543206106562221008 29 1 5402811237936853387 52 1 3884345269948184760 22 0 7873959847686200341 15 1 18396630536251250330 25 0 18230407003294263406 14...
output:
6531775129959975384 6212576544894999781 4191848452578359691 2769536540387251859 15526337103142577854 14948743844803225542 15235110724610778185 9004056994453026335 1028305510694260706 13496210650896843548 13961471020487846633 1864980030930734934 15243868808579626755 10451839696548403150 1178402342726...
result:
ok 19980 tokens
Test #8:
score: -100
Time Limit Exceeded
input:
20000 20000 400 41 15 1 10590708978689078436 33 0 17448869030270552656 37 1 16782453056389226553 2 1 18313039076194285622 53 1 7894371271572806769 60 1 14563226108042670650 56 0 12694119759311053234 12 1 969626878679760122 28 1 8906626075909573228 20 1 11632670066953088447 50 0 13097960756795495550 ...
output:
7425391644666486729 17533666397961516801 16986235811843827275 1784742314571007240 13192305384063626572 12739810377012216000 1179361465141596122 7698346401428161235 6903188112913915716 5380404381348976227 16126105607866972637 12798978320947566556 11234201442491665890 16073897288956866956 151328474491...