oj.uz

Submission #1090972

# Submission time Handle Problem Language Result Execution time Memory
1090972 2024-09-19T09:22:01 Z vjudge1 Topovi (COCI15_topovi) C++14
0 / 120
 380 ms 36684 KB 
// [COCI2015-2016#1] TOPOVI
#include <bits/stdc++.h>
using namespace std;
#define CAR const auto&
using LL = long long;
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int N, K, P;
  cin >> N >> K >> P;
  // if (N > 1000) {  // TODO: 优化
  //   return 0;
  // }
  unordered_map<int, int> R, C, RK, CK;
  using IP = array<int, 2>;
  map<IP, int> A;
  // R[r]/C[c]: 第r行/第c列的xor sum
  for (int i = 0, x, y, w; i < K and cin >> x >> y >> w; i++) {
    IP p{x, y};
    assert(!A.count(p));
    A[p] = w, R[x] ^= w, C[y] ^= w;
  }
  LL ans = 0;
  for (CAR p : R) ++RK[p.second];  // RK[k]: 有第几行 xor sum = k
  for (CAR p : C) ++CK[p.second];  // CK[k]: 有第几行 xor sum = k
  for (CAR p : CK) {
    int k = p.first, c = p.second;          // 有c列xor sum = k
    if (RK.count(k)) ans += LL(c) * RK[k];  // 有r行为k，对答案的贡献为r*c
  }
  auto cg_rk = [&](int r, int w) {  // RK[r] ^= w
    int x = R[r], y = x ^ w;        // 行r的 xor sum 从x 变化为 w
    ans -= CK.count(x) ? CK[x] : 0;
    ans += CK.count(y) ? CK[y] : 0;
    --RK[x], ++RK[y], R[r] = y;
  };
  auto cg_ck = [&](int c, int w) {  //
    int x = C[c], y = x ^ w;        // 列c的 xor sum 从x 变化为 w
    ans -= RK.count(x) ? RK[x] : 0;
    ans += RK.count(y) ? RK[y] : 0;
    --CK[x], ++CK[y], R[c] = y;
  };
  for (int i = 0, r1, c1, r2, c2; i < P and cin >> r1 >> c1 >> r2 >> c2; i++) {
    IP p1 = {r1, c1}, p2 = {r2, c2};
    assert(!A.count(p2));
    assert(A.count(p1));
    int w = A[p1];
    A.erase(p1), A[p2] = w;
    cg_rk(r1, w), cg_ck(c1, w), cg_rk(r2, w), cg_ck(c2, w);
    printf("%lld\n", ans);
  }
  return 0;
}
// ❓❓ 0

Subtask #1
0 / 120.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 45 ms 5532 KB Output isn't correct
7 Incorrect 31 ms 5576 KB Output isn't correct
8 Incorrect 25 ms 4368 KB Output isn't correct
9 Incorrect 26 ms 4616 KB Output isn't correct
10 Incorrect 31 ms 5132 KB Output isn't correct
11 Incorrect 344 ms 36564 KB Output isn't correct
12 Incorrect 327 ms 36508 KB Output isn't correct
13 Incorrect 340 ms 36572 KB Output isn't correct
14 Incorrect 307 ms 36516 KB Output isn't correct
15 Incorrect 339 ms 36684 KB Output isn't correct
16 Incorrect 349 ms 36516 KB Output isn't correct
17 Incorrect 323 ms 36560 KB Output isn't correct
18 Incorrect 338 ms 36512 KB Output isn't correct
19 Incorrect 313 ms 36520 KB Output isn't correct
20 Incorrect 380 ms 36592 KB Output isn't correct