QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227234 | #7190. Chessboard | PPP | WA | 1ms | 4064kb | C++17 | 4.6kb | 2023-10-27 04:07:15 | 2023-10-27 04:07:15 |
Judging History
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];
int info[4 * maxN][maxN][2];
int tp[maxN][maxN];
int q;
int MP[4 * maxN];
int SZ[4 * maxN];
int EDGE[2 * maxN][2 * maxN];
int CNT[4 * maxN];
int id[4 * maxN];
int Q[4 * maxN];
int ITER = 0;
int inter[4 * maxN];
void merge(int v, int l, int mid, int r) {
cnt_other[v] = cnt_other[2 * v] + cnt_other[2 * v + 1];
int SZ1 = SZ[2 * v];
int SZ2 = SZ[2 * v + 1];
memset(CNT, 0, sizeof CNT);
memset(id, -1, sizeof id);
int ANS = SZ1 + SZ2;
for (int x = 1; x <= m; x++) {
if (tp[mid][x] == tp[mid + 1][x]) {
int P = info[2 * v][x][1] * 2;
int Q = info[2 * v + 1][x][0] * 2 + 1;
if (CNT[P] > 0 && EDGE[P][CNT[P] - 1] == Q) continue;
if (CNT[Q] > 0 && EDGE[Q][CNT[Q] - 1] == P) continue;
ANS--;
EDGE[P][CNT[P]] = Q;
EDGE[Q][CNT[Q]] = P;
CNT[P]++;
CNT[Q]++;
}
}
if (v == 1) {
SZ[v] = 0;
cnt_other[v] += ANS;
return;
}
int CMP = 0;
for (int u = 0; u < SZ1; u++) {
if (id[2 * u] == -1) {
++CMP;
int topQ = 0;
Q[topQ++] = 2 * u;
id[2 * u] = 2 * u;
for (int z = 0; z < topQ; z++) {
int vert = Q[z];
for (int p = 0; p < CNT[vert]; p++) {
if (id[EDGE[vert][p]] == -1) {
ANS--;
id[EDGE[vert][p]] = 2 * u;
Q[topQ++] = EDGE[vert][p];
}
}
}
}
}
if (v == 1) {
SZ[v] = 0;
cnt_other[v] += ANS;
return;
}
for (int u = 0; u < SZ2; u++) {
if (id[2 * u + 1] == -1) {
++CMP;
id[2 * u + 1] = 2 * u + 1;
}
}
ITER++;
for (int x = 1; x <= m; x++) {
inter[id[info[2 * v][x][0] * 2]] = ITER;
inter[id[info[2 * v + 1][x][1] * 2 + 1]] = ITER;
}
int sz = 0;
for (int j = 0; j < 2 * SZ1; j += 2) {
if (inter[j] == ITER) {
CMP--;
MP[j] = sz;
sz++;
}
}
for (int j = 1; j < 2 * SZ2; j += 2) {
if (inter[j] == ITER) {
CMP--;
MP[j] = sz;
sz++;
}
}
cnt_other[v] += CMP;
for (int x = 1; x <= m; x++) {
info[v][x][0] = MP[id[info[2 * v][x][0] * 2]];
info[v][x][1] = MP[id[info[2 * v + 1][x][1] * 2 + 1]];
}
SZ[v] = sz;
}
void build(int v, int tl, int tr) {
if (tl == tr) {
cnt_other[v] = 0;
int sz = 0;
for (int j = 1; j <= m; j++) {
if (j == 1 || tp[tl][j] != tp[tl][j - 1]) {
info[v][j][0] = info[v][j][1] = sz;
sz++;
} else {
info[v][j][0] = info[v][j][1] = info[v][j - 1][0];
}
}
SZ[v] = sz;
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
merge(v, tl, tm, tr);
}
int calc() {
return SZ[1] + cnt_other[1];
}
void upd(int v, int tl, int tr, int pos) {
if (tl == tr) {
cnt_other[v] = 0;
int sz = 0;
for (int j = 1; j <= m; j++) {
if (j == 1 || tp[tl][j] != tp[tl][j - 1]) {
info[v][j][0] = info[v][j][1] = sz;
sz++;
} else {
info[v][j][0] = info[v][j][1] = info[v][j - 1][0];
}
}
SZ[v] = sz;
return;
}
int tm = (tl + tr) / 2;
if (pos <= tm) {
upd(2 * v, tl, tm, pos);
} else {
upd(2 * v + 1, tm + 1, tr, pos);
}
merge(v, tl, tm, tr);
}
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);
int op = calc();
while (q--) {
int x, y;
cin >> x >> y;
x ^= op;
y ^= op;
tp[x][y] ^= 1;
upd(1, 1, n, x);
op = calc();
cout << op << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3660kb
input:
2 2 2 01 10 5 5 0 0
output:
2 1
result:
ok 2 number(s): "2 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3664kb
input:
1 1 1 0 0 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 5 5 10111 11110 10010 00111 00101 4 1 5 4 12 11 12 13 13 9
output:
7 9 9 8 8
result:
ok 5 number(s): "7 9 9 8 8"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
5 5 5 00010 10000 11110 00001 01011 5 2 7 1 3 5 1 1 4 4
output:
5 6 5 6 6
result:
ok 5 number(s): "5 6 5 6 6"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
5 5 5 10010 10100 11100 11100 01000 0 4 1 7 1 1 4 0 7 6
output:
4 4 5 5 4
result:
ok 5 number(s): "4 4 5 5 4"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
5 5 5 00101 01011 00010 11000 01010 9 12 7 7 13 9 3 4 11 11
output:
6 8 7 9 7
result:
ok 5 number(s): "6 8 7 9 7"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
5 5 5 10101 00111 00100 10100 01000 10 12 9 11 6 4 10 12 10 12
output:
8 7 8 8 8
result:
ok 5 number(s): "8 7 8 8 8"
Test #8:
score: 0
Accepted
time: 0ms
memory: 3708kb
input:
5 5 5 01100 00001 11010 10010 01100 9 10 9 12 11 11 9 9 11 8
output:
8 9 10 10 9
result:
ok 5 number(s): "8 9 10 10 9"
Test #9:
score: 0
Accepted
time: 0ms
memory: 3648kb
input:
5 5 5 11011 11001 11111 11110 01111 0 1 2 1 2 2 2 2 2 2
output:
3 3 3 3 3
result:
ok 5 number(s): "3 3 3 3 3"
Test #10:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
5 5 5 01011 10101 00001 00011 01101 13 10 10 13 13 12 15 9 9 9
output:
8 9 12 10 10
result:
ok 5 number(s): "8 9 12 10 10"
Test #11:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
5 5 5 11010 10011 00011 00111 00111 0 1 1 0 6 1 0 1 1 7
output:
5 4 4 5 5
result:
ok 5 number(s): "5 4 4 5 5"
Test #12:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
5 5 5 11100 10011 01001 01010 01110 6 3 2 7 4 6 0 1 7 3
output:
6 7 5 6 5
result:
ok 5 number(s): "6 7 5 6 5"
Test #13:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
10 10 10 0010011100 1010001100 0100110111 1000011111 1000000110 1110000011 0010111100 0100011001 1110100001 0001101100 17 17 20 19 25 20 18 18 23 17 24 16 20 23 22 20 26 22 26 20
output:
17 17 16 18 18 19 19 19 19 19
result:
ok 10 numbers
Test #14:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
10 10 10 1110001110 0101101010 1111101001 1011101110 0000111100 1001100100 1000101000 0000111011 1111001010 1101000011 10 14 10 9 12 6 5 4 6 15 7 12 10 15 10 6 11 5 13 11
output:
14 15 13 14 13 14 15 15 15 14
result:
ok 10 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
10 10 10 1100011101 0110001100 1111110101 0001010001 0110010110 1101100100 1101010000 1101110001 0010110110 1110101111 22 19 19 22 29 17 17 28 19 17 19 20 31 23 19 20 18 29 28 22
output:
21 20 21 21 23 22 21 21 21 19
result:
ok 10 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
10 10 10 0000001110 1001110001 0100111111 0010110100 0110101110 1110011011 1011000110 1000011001 0011001101 0010001000 24 23 17 28 21 30 28 29 29 24 24 20 17 29 18 25 17 28 24 19
output:
20 22 24 25 28 24 24 25 25 23
result:
ok 10 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3692kb
input:
10 10 10 1000110010 1100010111 0100100011 1010000010 1110010101 1010011110 0011110011 1100011011 1011000101 1110100100 17 28 21 30 28 18 19 30 16 17 19 29 19 20 30 17 31 17 21 16
output:
22 22 20 20 21 23 22 21 23 23
result:
ok 10 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
10 10 10 0010110001 1111100001 0011111101 1001011011 1110111101 1101111101 0101101101 0001110001 0010111100 1011000011 22 23 19 20 22 26 21 22 19 21 26 18 12 13 21 23 21 25 21 22
output:
17 18 16 17 16 15 16 16 16 16
result:
ok 10 numbers
Test #19:
score: 0
Accepted
time: 0ms
memory: 3752kb
input:
10 10 10 1110100010 0001000100 1001001000 1011111100 0110001111 1011110000 1001011001 0101111111 0011000010 0111101011 22 19 18 28 31 18 29 17 28 19 31 22 31 17 20 17 31 18 18 20
output:
21 21 20 20 21 23 23 23 22 21
result:
ok 10 numbers
Test #20:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
10 10 10 1110110000 0010101110 1000010010 0100000001 0000110101 1110010001 1001100111 0000010101 1000101011 0010011100 17 17 19 30 16 22 17 31 16 23 19 18 17 28 24 27 19 24 24 26
output:
22 21 22 22 23 24 25 26 27 25
result:
ok 10 numbers
Test #21:
score: 0
Accepted
time: 0ms
memory: 3756kb
input:
10 10 10 0000000011 1111011001 0010001110 0111110111 0000011101 1000010110 1111110111 1000010111 1000010011 1110110000 12 0 13 11 8 15 0 15 12 2 14 0 8 15 12 9 10 10 15 3
output:
9 9 10 10 10 11 11 11 11 12
result:
ok 10 numbers
Test #22:
score: 0
Accepted
time: 0ms
memory: 3676kb
input:
10 10 10 1010000001 0111001100 1011001001 1011110010 0110011011 0110000111 0110000011 1111110001 0100001110 0000001110 18 18 22 18 21 22 26 24 24 16 21 19 23 22 17 21 17 21 25 17
output:
17 17 16 17 17 16 16 18 19 20
result:
ok 10 numbers
Test #23:
score: 0
Accepted
time: 1ms
memory: 4052kb
input:
50 50 50 11110010100001100100010000100100010111001101010111 00100110100101010011100111011101000110001111111111 00000100111011001011110101001011101111100100101011 00010001110010011110001100001100100001110111111001 01001010010100010000101100111000011010101000001101 110000110101110010011011110101100101...
output:
370 371 373 373 371 373 374 376 374 373 372 372 374 374 372 373 373 373 372 372 373 373 374 373 373 372 372 374 375 376 374 373 374 374 374 373 373 373 373 376 376 376 377 377 378 379 380 379 378 378
result:
ok 50 numbers
Test #24:
score: 0
Accepted
time: 0ms
memory: 4052kb
input:
50 50 50 10110110011010000110111101011100011110111001101111 01000111110100100111110001010001011000110000011111 01000111101101000100100110011101001100111011110100 00110110111110001111010011111101110100111101110011 00011001010000011001000100110010110111010011110111 110101110111001000100100110000111101...
output:
346 346 349 349 350 351 350 350 348 349 348 347 348 348 349 348 348 349 349 349 349 348 346 346 347 346 344 343 342 344 345 345 344 342 344 343 343 345 345 345 345 345 346 345 345 345 345 344 344 342
result:
ok 50 numbers
Test #25:
score: 0
Accepted
time: 1ms
memory: 4040kb
input:
50 50 50 00011010101101101011111100101110101001110011010101 00111111101010011101000001111011010010110100110000 10110011011110001111100101001101110110010101001010 10011011011011001011101000010000111011011111101111 01110000111110011110110100110100100011011100000000 010110001001010001110111110110110001...
output:
396 395 396 395 397 396 397 396 396 396 395 395 395 395 395 397 399 399 399 398 398 400 399 400 400 401 401 402 400 403 403 403 403 402 402 403 405 407 407 405 405 405 405 406 405 404 404 404 404 405
result:
ok 50 numbers
Test #26:
score: 0
Accepted
time: 1ms
memory: 3988kb
input:
50 50 50 10011110100010011101000111010110010100000011111101 00111100011110001001000111011011001101101000010110 01010010011110101000111100001110110000000000110111 01111100011011010010100111110001111111101110100000 00100011111111110011000100101110110010000101010010 101101010111101011001000011010101101...
output:
362 365 366 365 367 369 367 366 366 366 362 363 363 364 365 365 365 366 366 365 366 366 366 366 368 370 369 368 368 370 371 371 370 368 367 367 365 364 364 365 365 366 367 366 365 364 364 364 363 364
result:
ok 50 numbers
Test #27:
score: 0
Accepted
time: 1ms
memory: 4044kb
input:
50 50 50 01111000010011111011000011110110111101010011000111 01000100000100111111010111010001010011000101101011 10001010001000100111001111010000001011101110101001 01001011011101000000111000001100010100001100110110 01011010111001110100001101100100110101000111101100 001100100101000011011010001111100011...
output:
373 376 377 376 374 370 370 369 368 367 366 366 366 362 362 362 361 364 364 364 363 363 363 365 366 367 369 368 369 368 369 369 368 369 370 371 371 370 369 372 371 371 371 372 372 369 370 367 367 368
result:
ok 50 numbers
Test #28:
score: -100
Wrong Answer
time: 1ms
memory: 4064kb
input:
50 50 50 11111100101101000110101010001000000011101011111100 00000001110000100011100001111011000001010001001101 01101100011010111000011100000010001101110001011110 11101111110000000001101011101101000011010110111110 00000001100001101001111101101010101000111000111111 101110111011110001101101001011110111...
output:
340 338 338 338 338 339 340 339 339 338 339 339 339 339 338 340 338 340 339 338 337 337 337 337 335 335 336 337 338 337 335 332 335 336 335 335 335 337 333 333 335 334 333 332 332 333 332 330 328 327
result:
wrong answer 1st numbers differ - expected: '343', found: '340'