QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#662065#8335. Fast Hash TransformrizynvuWA 4ms44556kbC++142.4kb2024-10-20 20:25:412024-10-20 20:25:53

Judging History

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

  • [2024-10-20 20:25:53]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:44556kb
  • [2024-10-20 20:25:41]
  • 提交

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'