Submission #1090979

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090979		vjudge1	Topovi (COCI15_topovi)	C++14	120 / 120	347 ms	32484 KiB

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 / 120