QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#468731 | #8335. Fast Hash Transform | real_sigma_team# | TL | 4595ms | 34612kb | C++23 | 7.7kb | 2024-07-08 23:52:19 | 2024-07-08 23:52:19 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
using namespace std;
using ll = long long;
struct SqrtTreeItem {
array<uint64_t, 64> arr;
uint64_t xr = 0;
SqrtTreeItem() {
arr.fill(0);
xr = 0;
}
};
SqrtTreeItem op(const SqrtTreeItem &a, const SqrtTreeItem &b) {
SqrtTreeItem res;
res.xr = b.xr;
for (int i = 0; i < 64; ++i) {
for (int j = 0; j < 64; ++j) {
if (b.arr[i] >> j & 1) {
res.xr ^= (a.xr >> j & 1) << i;
res.arr[i] ^= a.arr[j];
}
}
}
return res;
}
inline int log2Up(int n) {
int res = 0;
while ((1 << res) < n) {
res++;
}
return res;
}
class SqrtTree {
private:
int n, lg, indexSz;
vector<SqrtTreeItem> v;
vector<int> clz, layers, onLayer;
vector< vector<SqrtTreeItem> > pref, suf, between;
inline void buildBlock(int layer, int l, int r) {
pref[layer][l] = v[l];
for (int i = l+1; i < r; i++) {
pref[layer][i] = op(pref[layer][i-1], v[i]);
}
suf[layer][r-1] = v[r-1];
for (int i = r-2; i >= l; i--) {
suf[layer][i] = op(v[i], suf[layer][i+1]);
}
}
inline void buildBetween(int layer, int lBound, int rBound, int betweenOffs) {
int bSzLog = (layers[layer]+1) >> 1;
int bCntLog = layers[layer] >> 1;
int bSz = 1 << bSzLog;
int bCnt = (rBound - lBound + bSz - 1) >> bSzLog;
for (int i = 0; i < bCnt; i++) {
SqrtTreeItem ans;
for (int j = i; j < bCnt; j++) {
SqrtTreeItem add = suf[layer][lBound + (j << bSzLog)];
ans = (i == j) ? add : op(ans, add);
between[layer-1][betweenOffs + lBound + (i << bCntLog) + j] = ans;
}
}
}
inline void buildBetweenZero() {
int bSzLog = (lg+1) >> 1;
for (int i = 0; i < indexSz; i++) {
v[n+i] = suf[0][i << bSzLog];
}
build(1, n, n + indexSz, (1 << lg) - n);
}
inline void updateBetweenZero(int bid) {
int bSzLog = (lg+1) >> 1;
v[n+bid] = suf[0][bid << bSzLog];
update(1, n, n + indexSz, (1 << lg) - n, n+bid);
}
void build(int layer, int lBound, int rBound, int betweenOffs) {
if (layer >= (int)layers.size()) {
return;
}
int bSz = 1 << ((layers[layer]+1) >> 1);
for (int l = lBound; l < rBound; l += bSz) {
int r = min(l + bSz, rBound);
buildBlock(layer, l, r);
build(layer+1, l, r, betweenOffs);
}
if (layer == 0) {
buildBetweenZero();
} else {
buildBetween(layer, lBound, rBound, betweenOffs);
}
}
void update(int layer, int lBound, int rBound, int betweenOffs, int x) {
if (layer >= (int)layers.size()) {
return;
}
int bSzLog = (layers[layer]+1) >> 1;
int bSz = 1 << bSzLog;
int blockIdx = (x - lBound) >> bSzLog;
int l = lBound + (blockIdx << bSzLog);
int r = min(l + bSz, rBound);
buildBlock(layer, l, r);
if (layer == 0) {
updateBetweenZero(blockIdx);
} else {
buildBetween(layer, lBound, rBound, betweenOffs);
}
update(layer+1, l, r, betweenOffs, x);
}
inline SqrtTreeItem query(int l, int r, int betweenOffs, int base) {
if (l == r) {
return v[l];
}
if (l + 1 == r) {
return op(v[l], v[r]);
}
int layer = onLayer[clz[(l - base) ^ (r - base)]];
int bSzLog = (layers[layer]+1) >> 1;
int bCntLog = layers[layer] >> 1;
int lBound = (((l - base) >> layers[layer]) << layers[layer]) + base;
int lBlock = ((l - lBound) >> bSzLog) + 1;
int rBlock = ((r - lBound) >> bSzLog) - 1;
SqrtTreeItem ans = suf[layer][l];
if (lBlock <= rBlock) {
SqrtTreeItem add = (layer == 0) ? (
query(n + lBlock, n + rBlock, (1 << lg) - n, n)
) : (
between[layer-1][betweenOffs + lBound + (lBlock << bCntLog) + rBlock]
);
ans = op(ans, add);
}
ans = op(ans, pref[layer][r]);
return ans;
}
public:
inline SqrtTreeItem query(int l, int r) {
return query(l, r, 0, 0);
}
inline void update(int x, const SqrtTreeItem &item) {
v[x] = item;
update(0, 0, n, 0, x);
}
SqrtTree(const vector<SqrtTreeItem>& a)
: n((int)a.size()), lg(log2Up(n)), v(a), clz(1 << lg), onLayer(lg+1) {
clz[0] = 0;
for (int i = 1; i < (int)clz.size(); i++) {
clz[i] = clz[i >> 1] + 1;
}
int tlg = lg;
while (tlg > 1) {
onLayer[tlg] = (int)layers.size();
layers.push_back(tlg);
tlg = (tlg+1) >> 1;
}
for (int i = lg-1; i >= 0; i--) {
onLayer[i] = max(onLayer[i], onLayer[i+1]);
}
int betweenLayers = max(0, (int)layers.size() - 1);
int bSzLog = (lg+1) >> 1;
int bSz = 1 << bSzLog;
indexSz = (n + bSz - 1) >> bSzLog;
v.resize(n + indexSz);
pref.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
suf.assign(layers.size(), vector<SqrtTreeItem>(n + indexSz));
between.assign(betweenLayers, vector<SqrtTreeItem>((1 << lg) + bSz));
build(0, 0, n, 0);
}
};
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, q, c;
cin >> n >> q >> c;
vector<SqrtTreeItem> a(n);
for (int i = 0; i < n; ++i) {
int m;
cin >> m;
vector<tuple<int, int, uint64_t>> res(m);
for (auto& [s, o, A] : res) cin >> s >> o >> A;
cin >> a[i].xr;
for (int j = 0; j < 64; ++j) {
for (auto [s, o, A] : res) {
int k = j + s;
if (k >= 64) k -= 64;
if (o == 0 && (A >> k & 1)) a[i].xr ^= 1ull << k;
else if (o == 1 && (~A >> k & 1)) {}
else {
a[i].arr[k] ^= 1ull << j;
}
}
}
}
SqrtTree tr(a);
while (q--) {
int op;
cin >> op;
if (op == 0) {
int l, r;
uint64_t x;
cin >> l >> r >> x;
--l, --r;
auto v = tr.query(l, r);
uint64_t res = v.xr;
for (int j = 0; j < 64; ++j) {
for (int k = 0; k < 64; ++k) {
if (v.arr[j] >> k & 1) {
res ^= (x >> k & 1) << j;
}
}
}
cout << res << '\n';
} else {
int i;
cin >> i;
--i;
a[i] = SqrtTreeItem();
int m;
cin >> m;
vector<tuple<int, int, uint64_t>> res(m);
for (auto& [s, o, A] : res) cin >> s >> o >> A;
cin >> a[i].xr;
for (int j = 0; j < 64; ++j) {
for (auto [s, o, A] : res) {
int k = j + s;
if (k >= 64) k -= 64;
if (o == 0 && (A >> k & 1)) a[i].xr ^= 1ull << k;
else if (o == 1 && (~A >> k & 1)) {}
else {
a[i].arr[k] ^= 1ull << j;
}
}
}
tr.update(i, a[i]);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3640kb
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: 2ms
memory: 3920kb
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: 88ms
memory: 3580kb
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: 2553ms
memory: 7344kb
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: 4595ms
memory: 34612kb
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...