QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#563407#8335. Fast Hash TransformUnique_HanpiTL 13ms4000kbC++142.7kb2024-09-14 11:23:002024-09-14 11:23:02

Judging History

你现在查看的是最新测评结果

  • [2024-09-14 11:23:02]
  • 评测
  • 测评结果:TL
  • 用时:13ms
  • 内存:4000kb
  • [2024-09-14 11:23:00]
  • 提交

answer

#include <bits/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
using namespace std;

typedef unsigned long long ll;
const int N = 20005;
const int B = 500;
const int Mod = 998244353;

int n, q, c;
int loc[N], L[N], R[N];
int s[64], o[64];
ll A[64], BB;

struct f {
    bool b[64];
    ll c[64];

    inline ll calc(ll x) {
        ll ret = 0;
        for (int i = 0; i < 64; i++)
            ret |= (ll(b[i] ^ (__builtin_popcountll(x & c[i]) & 1)) << i);
        return ret;
    }
} H[N], F[N / B + 2], sf[N / B + 2], pf[N / B + 2];

inline f merge(const f &A, const f &B) {//A after B
    f r;
    for (int i = 0; i < 64; i++) {
        r.c[i] = 0;
        r.b[i] = A.b[i];
        for (int j = 0; j < 64; j++) if ((A.c[i] >> j) & 1)
            r.c[i] ^= B.c[j], r.b[i] ^= B.b[j];
    }
    return r;
}

inline void rebuild(int id) {
    int l = L[id], r = R[id];
    F[id] = H[l];
    pf[l] = H[l];
    for (int i = l + 1; i <= r; i++) {
        F[id] = merge(H[i], F[id]);
        pf[i] = merge(H[i], pf[i]);
    }
    sf[r] = H[r];
    for (int i = r - 1; i >= l; i--) sf[i] = merge(sf[i], H[i]);
}

inline void read(f &a) {
    int m;
    scanf("%d", &m);
    for (int i = 1; i <= m; i++) scanf("%d", &s[i]), scanf("%d", &o[i]), scanf("%llu", &A[i]);
    scanf("%llu", &BB);

    for (int i = 0; i < 64; i++) {
        a.b[i] = (BB >> i) & 1;
        a.c[i] = 0;
        for (int j = 1; j <= m; j++) {
            int x = (i - s[j] + 64) % 64;
            if (o[j] == 0 && (A[j] >> i & 1)) a.b[i] ^= 1;
            else if (o[j] == 1 && !(A[j] >> i & 1)) ;
            else a.c[i] |= (ll(1) << x);
        }
    }
}

int main() {
    scanf("%d%d%d", &n, &q, &c);

    for (int i = 1; i <= n; i++) {
        loc[i] = i / B + 1;
        if (loc[i] != loc[i - 1]) L[loc[i]] = i;
        R[loc[i]] = i;
    }

    for (int i = 1; i <= n; i++) read(H[i]);

    for (int i = 1; i <= loc[n]; i++) rebuild(i);

    while (q--) {
        int op, l, r; ll x;
        scanf("%d", &op);
        if (op == 0) {
            scanf("%d%d%llu", &l, &r, &x);
            int lb = loc[l], rb = loc[r];
            if (lb == rb) {
                for (int i = l; i <= r; i++) x = H[i].calc(x);
                printf("%llu\n", x);
            } else {
                x = sf[l].calc(x);
                for (int i = lb + 1; i < rb; i++) x = F[i].calc(i);
                x = pf[r].calc(x);
                printf("%llu\n", x);
            }
        } else {
            scanf("%d", &l);
            read(H[l]);
            rebuild(loc[l]);
        }
    }
    return 0;
}
/*
 3 1 1
 1 4 0 0 51966
 2 0 0 15 61 1 4095 46681
 1 0 0 16 15
 0 1 3 2023
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3992kb

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: 4000kb

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: 13ms
memory: 3852kb

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: -100
Time Limit Exceeded

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:

5250920776524142232
3955689385921811425
3274374696028828967
4053604616567819123
7060760694699414253
3657813567347280558
17878972494087474757
14828244200736700791
4174217412272688828
2130623540765458773
2840709292846591354
2059615555491319585
16681943101658342515
11881139695289515494
8921126582692922...

result: