QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227652 | #7190. Chessboard | PPP | ML | 0ms | 0kb | C++17 | 5.9kb | 2023-10-27 20:43:14 | 2023-10-27 20:43:14 |
answer
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
typedef long long ll;
typedef double ld;
int n, m;
const int maxN = 205;
int cnt_other[4 * maxN];
vector<int> L[16 * maxN * maxN], R[16 * maxN * maxN], U[16 * maxN * maxN], D[16 * maxN * maxN];
int SZ[16 * maxN * maxN];
int tp[maxN][maxN];
int q;
int par[4 * maxN];
int get(int x) {
if (x == par[x]) return x;
return par[x] = get(par[x]);
}
void unite(int a, int b) {
a = get(a);
b = get(b);
if (a == b) return;
par[a] = b;
}
bool was[4 * maxN];
int MP[4 * maxN];
void merge_y(int v, int lx, int rx, int ly, int my, int ry) {
cnt_other[v] = cnt_other[2 * v] + cnt_other[2 * v + 1];
//merge U, D
int SZ1 = SZ[2 * v];
int SZ2 = SZ[2 * v + 1];
for (int u = 0; u < SZ1 + SZ2; u++) {
par[u] = u;
was[u] = false;
}
for (int x = lx; x <= rx; x++) {
if (tp[x][my] == tp[x][my + 1]) {
unite(R[2 * v][x - lx], L[2 * v + 1][x - lx] + SZ1);
}
}
for (int x = lx; x <= rx; x++) {
was[get(L[2 * v][x - lx])] = true;
was[get(R[2 * v + 1][x - lx] + SZ1)] = true;
}
for (int x = ly; x <= my; x++) {
was[get(D[2 * v][x - ly])] = true;
was[get(U[2 * v][x - ly])] = true;
}
for (int x = my + 1; x <= ry; x++) {
was[get(D[2 * v + 1][x - my - 1] + SZ1)] = true;
was[get(U[2 * v + 1][x - my - 1] + SZ1)] = true;
}
int sz = 0;
for (int u = 0; u < SZ1 + SZ2; u++) {
if (get(u) == u) {
if (!was[u]) {
cnt_other[v]++;
}
else {
MP[u] = sz;
sz++;
}
}
}
SZ[v] = sz;
for (int x = lx; x <= rx; x++) {
L[v][x - lx] = MP[get(L[2 * v][x - lx])];
R[v][x - lx] = MP[get(R[2 * v + 1][x - lx] + SZ1)];
}
for (int x = ly; x <= my; x++) {
U[v][x - ly] = MP[get(U[2 * v][x - ly])];
D[v][x - ly] = MP[get(D[2 * v][x - ly])];
}
for (int x = my + 1; x <= ry; x++) {
U[v][x - ly] = MP[get(U[2 * v + 1][x - my - 1] + SZ1)];
D[v][x - ly] = MP[get(D[2 * v + 1][x - my - 1] + SZ1)];
}
}
void merge_x(int v, int lx, int mx, int rx, int ly, int ry) {
cnt_other[v] = cnt_other[2 * v] + cnt_other[2 * v + 1];
//merge U, D
int SZ1 = SZ[2 * v];
int SZ2 = SZ[2 * v + 1];
for (int u = 0; u < SZ1 + SZ2; u++) {
par[u] = u;
was[u] = false;
}
for (int x = ly; x <= ry; x++) {
if (tp[mx][x] == tp[mx + 1][x]) {
unite(D[2 * v][x - ly], U[2 * v + 1][x - ly] + SZ1);
}
}
for (int x = ly; x <= ry; x++) {
was[get(U[2 * v][x - ly])] = true;
was[get(D[2 * v + 1][x - ly] + SZ1)] = true;
}
for (int x = lx; x <= mx; x++) {
was[get(L[2 * v][x - lx])] = true;
was[get(R[2 * v][x - lx])] = true;
}
for (int x = mx + 1; x <= rx; x++) {
was[get(L[2 * v + 1][x - mx - 1] + SZ1)] = true;
was[get(R[2 * v + 1][x - mx - 1] + SZ1)] = true;
}
int sz = 0;
for (int u = 0; u < SZ1 + SZ2; u++) {
if (get(u) == u) {
if (!was[u]) {
cnt_other[v]++;
}
else {
MP[u] = sz;
sz++;
}
}
}
SZ[v] = sz;
for (int x = ly; x <= ry; x++) {
U[v][x - ly] = MP[get(U[2 * v][x - ly])];
D[v][x - ly] = MP[get(D[2 * v + 1][x - ly] + SZ1)];
}
for (int x = lx; x <= mx; x++) {
L[v][x - lx] = MP[get(L[2 * v][x - lx])];
R[v][x - lx] = MP[get(R[2 * v][x - lx])];
}
for (int x = mx + 1; x <= rx; x++) {
L[v][x - lx] = MP[get(L[2 * v + 1][x - mx - 1] + SZ1)];
R[v][x - lx] = MP[get(R[2 * v + 1][x - mx - 1] + SZ1)];
}
}
void build(int v, int lx, int rx, int ly, int ry) {
if (lx == rx && ly == ry) {
cnt_other[v] = 0;
L[v] = {0};
R[v] = {0};
D[v] = {0};
U[v] = {0};
SZ[v] = 1;
return;
}
U[v].resize(ry - ly + 1);
D[v].resize(ry - ly + 1);
L[v].resize(rx - lx + 1);
R[v].resize(rx - lx + 1);
if (rx - lx < ry - ly) {
int my = (ly + ry) / 2;
build(2 * v, lx, rx, ly, my);
build(2 * v + 1, lx, rx, my + 1, ry);
merge_y(v, lx, rx, ly, my, ry);
}
else {
int mx = (lx + rx) / 2;
build(2 * v, lx, mx, ly, ry);
build(2 * v + 1, mx + 1, rx, ly, ry);
merge_x(v, lx, mx, rx, ly, ry);
}
}
int calc() {
return cnt_other[1] + SZ[1];
}
void upd(int v, int lx, int rx, int ly, int ry, int px, int py) {
if (lx == rx && ly == ry) {
return;
}
if (rx - lx < ry - ly) {
int my = (ly + ry) / 2;
if (py <= my) upd(2 * v, lx, rx, ly, my, px, py);
else upd(2 * v + 1, lx, rx, my + 1, ry, px, py);
merge_y(v, lx, rx, ly, my, ry);
}
else {
int mx = (lx + rx) / 2;
if (px <= mx) upd(2 * v, lx, mx, ly, ry, px, py);
else upd(2 * v + 1, mx + 1, rx, ly, ry, px, py);
merge_x(v, lx, mx, rx, ly, ry);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m >> q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
char c;
cin >> c;
if (c == '1') tp[i][j] = 1;
}
}
build(1, 1, n, 1, m);
int op = calc();
while (q--) {
int x, y;
cin >> x >> y;
x ^= op;
y ^= op;
tp[x][y] ^= 1;
upd(1, 1, n, 1, m, x, y);
op = calc();
cout << op << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Memory Limit Exceeded
input:
2 2 2 01 10 5 5 0 0
output:
2 1