Submission #1090979

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1090979	2024-09-19T09:57:23 Z	vjudge1	Topovi (COCI15_topovi)	C++14	120 / 120	347 ms	32484 KB

topovi

// [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);
  LL N, K, P;
  cin >> N >> K >> P;  // R[r]/C[c]: 第r行/第c列的xor sum
  unordered_map<int, LL> R, C, RK{{0, N}}, CK{{0, N}};
  using IP = array<int, 2>;
  map<IP, int> A;
  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;
  }
  auto m_get = [](unordered_map<int, LL> &MK, int k) {
    return MK.count(k) ? MK[k] : 0ll;
  };
  LL ans = 0;
  for (CAR p : R) ++RK[p.second], --RK[0];  // RK[k]: 有第几行 xor sum = k
  for (CAR p : C) ++CK[p.second], --CK[0];  // CK[k]: 有第几行 xor sum = k
  for (CAR p : RK) {                        // 有r行xor sum = k
    LL k = p.first, r = p.second;  // 有c列为k，对答案的贡献为r*(N-c)
    ans += r * (N - m_get(CK, k));
  }
  auto cg_rk = [&](int r, int w) {  // R[r] ^= w
    LL &x = R[r], y = x ^ w;        // 行r的 xor sum 从x 变化为 w
    ans += (N - m_get(CK, y)) - (N - m_get(CK, x));
    --RK[x], ++RK[y], x = y;
  };
  auto cg_ck = [&](int c, int w) {
    LL &x = C[c], y = x ^ w;  // 列c的 xor sum 从x 变化为 w
    ans += (N - m_get(RK, y)) - (N - m_get(RK, x));
    --CK[x], ++CK[y], x = 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;
}
// AC 100

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	36 ms	4640 KB	Output is correct
7	Correct	30 ms	4372 KB	Output is correct
8	Correct	24 ms	3964 KB	Output is correct
9	Correct	26 ms	3956 KB	Output is correct
10	Correct	26 ms	3900 KB	Output is correct
11	Correct	320 ms	32412 KB	Output is correct
12	Correct	310 ms	32484 KB	Output is correct
13	Correct	306 ms	32424 KB	Output is correct
14	Correct	324 ms	32420 KB	Output is correct
15	Correct	318 ms	32408 KB	Output is correct
16	Correct	322 ms	32356 KB	Output is correct
17	Correct	347 ms	32416 KB	Output is correct
18	Correct	299 ms	32420 KB	Output is correct
19	Correct	326 ms	32416 KB	Output is correct
20	Correct	322 ms	32416 KB	Output is correct