QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227652#7190. ChessboardPPPML 0ms0kbC++175.9kb2023-10-27 20:43:142023-10-27 20:43:14

Judging History

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

  • [2023-10-27 20:43:14]
  • 评测
  • 测评结果:ML
  • 用时:0ms
  • 内存:0kb
  • [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

result: