QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#463391#8335. Fast Hash TransformPlentyOfPenaltyWA 2ms7764kbC++204.1kb2024-07-04 19:44:122024-07-04 19:44:12

Judging History

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

  • [2024-07-04 19:44:12]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:7764kb
  • [2024-07-04 19:44:12]
  • 提交

answer

#include <bits/stdc++.h>
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define log(...) (void(0))
#define endl '\n'
#endif
using namespace std;
using ull = unsigned long long;

#define at(x, i) (((x) >> (i)) & 1)

const int N = 2e4 + 9;
int n, q, c;
ull b[N];

inline void output(ull x) {
  for (unsigned int i = 0; i < 64; i++) {
    log("%d", (int)at(x, i));
  }
  log("\n");
}

struct matrix {
  ull a[64], b[64];
  void clear() {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
  }
  void output() {
    assert(self_check());
    for (unsigned int i = 0; i < 64; i++) {
      for (unsigned int j = 0; j < 64; j++) {
        log("%d", (int)at(a[j], i));
      }
      log("\n");
    }
  }
  bool self_check() const {
    for (unsigned int i = 0; i < 64; i++)
      for (unsigned int j = 0; j < 64; j++)
        if (at(a[i], j) != at(b[j], i)) {
          return false;
        }
    return true;
  }
  void set(int i, int j) { // i?j?
    a[j] |= 1ull << i;
    b[i] |= 1ull << j;
  }
  matrix operator+(matrix rhs) const {
    for (unsigned int i = 0; i < 64; i++) {
      rhs.a[i] ^= a[i];
      rhs.b[i] ^= b[i];
    }
    assert(rhs.self_check());
    return rhs;
  }
  matrix operator*(const matrix &rhs) const {
    static matrix c;
    c.clear();
    for (int i = 0; i < 64; ++i) {
      for (int j = 0; j < 64; ++j) {
        ull fl = __builtin_popcount(b[i] & rhs.a[j]) & 1;
        c.a[j] |= (fl << i);
        c.b[i] |= (fl << j);
      }
    }
    assert(c.self_check());
    return c;
  }
} op[N];

matrix from_vec(ull v) {
  static matrix c;
  c.clear();
  c.a[0] = v;
  for (unsigned int i = 0; i < 64; i++) {
    c.b[i] = (v >> i) & 1;
  }
  return c;
}

struct atom {
  matrix x, c;
};
inline atom merge(const atom &l, const atom &r) { return atom{r.x * l.x, r.c + r.x * l.c}; }

struct segment {
  int l, r, mid;
  atom dat;
} p[N << 2];

void build(int u, int l, int r) {
  p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
  if (l == r) {
    p[u].dat = {op[l], from_vec(b[l])};
    // log("c[%d:%d]: ", p[u].l, p[u].r), output(p[u].dat.c.a[0]);
    return;
  }
  build(u << 1, l, p[u].mid);
  build(u << 1 | 1, p[u].mid + 1, r);
  p[u].dat = merge(p[u << 1].dat, p[u << 1 | 1].dat);
  // log("c[%d:%d]: ", p[u].l, p[u].r), output(p[u].dat.c.a[0]);
}

void modify(int u, int k) {
  if (p[u].l == p[u].r) {
    p[u].dat = {op[k], from_vec(b[k])};
    return;
  }
  if (k <= p[u].mid) {
    modify(u << 1, k);
  } else {
    modify(u << 1 | 1, k);
  }
  p[u].dat = merge(p[u << 1].dat, p[u << 1 | 1].dat);
}

atom query(int u, int l, int r) {
  // log("query %d %d %d\n", u, l, r);
  if (p[u].l == l && p[u].r == r) {
    return p[u].dat;
  }
  if (r <= p[u].mid) return query(u << 1, l, r);
  if (l > p[u].mid) return query(u << 1 | 1, l, r);
  return merge(query(u << 1, l, p[u].mid), query(u << 1 | 1, p[u].mid + 1, r));
}

void read_oper(matrix &op, ull &b) {
  op.clear();
  int m;
  cin >> m;
  vector<int> s(m), o(m);
  vector<ull> a(m);
  for (int i = 0; i < m; i++) {
    cin >> s[i] >> o[i] >> a[i];
    // log(">> %d %d %llu\n", s[i], o[i], a[i]);
  }
  cin >> b;
  for (int i = 0; i < m; i++) {
    if (o[i] == 0) {
      for (int j = 0; j < 64; j++) {
        if (at(a[i], j)) {
          b ^= 1ull << j;
        }
        a[i] ^= 1ull << j;
      }
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < 64; j++)
      if (at(a[i], j)) {
        op.set(j, (j - s[i] + 64) % 64);
      }
  }
}

int main() {
#ifdef memset0
  freopen("H.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q >> c;
  for (int i = 1; i <= n; i++) {
    read_oper(op[i], b[i]);
  }
  build(1, 1, n);
  for (int o, k, l, r, i = 1; i <= q; i++) {
    cin >> o;
    if (o == 0) {
      ull x;
      cin >> l >> r >> x;
      atom res = query(1, l, r);
      matrix s = res.c + res.x * from_vec(x);
      // res.x.output();
      cout << s.a[0] << endl;
      // log("x: "), output(x);
      // log("s: "), output(s.a[0]);
      // log("c: "), output(res.c.a[0]);
      // log("t: "), output((res.x * from_vec(x)).a[0]);
    } else {
      cin >> k;
      read_oper(op[k], b[k]);
      modify(1, k);
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 2ms
memory: 5752kb

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:

10735028597927780461
6286254107986266013
2891025415212112008
5292801977632587806
16546994779959756186
17580801933839203485

result:

wrong answer 1st words differ - expected: '9487331362121050549', found: '10735028597927780461'