QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#227183 | #7190. Chessboard | PPP# | RE | 1ms | 3972kb | C++17 | 3.7kb | 2023-10-27 01:04:02 | 2023-10-27 01:04:03 |
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 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(int v, int l, int mid, int r) {
cnt_other[v] = cnt_other[2 * v] + cnt_other[2 * v + 1];
int SZ1 = 0;
for (int x = 1; x <= m; x++) {
SZ1 = max(SZ1, info[2 * v][x][0]);
SZ1 = max(SZ1, info[2 * v][x][1]);
}
SZ1++;
int SZ2 = 0;
for (int x = 1; x <= m; x++) {
SZ2 = max(SZ2, info[2 * v + 1][x][0]);
SZ2 = max(SZ2, info[2 * v + 1][x][1]);
}
SZ2++;
for (int u = 0; u < SZ1 + SZ2; u++) {
par[u] = u;
}
for (int x = 1; x <= m; x++) {
if (tp[mid][x] == tp[mid + 1][x]) {
unite(info[2 * v][x][1], info[2 * v + 1][x][0] + SZ1);
}
}
for (int x = 1; x <= m; x++) {
was[get(info[2 * v][x][0])] = true;
was[get(info[2 * v + 1][x][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++;
}
}
}
for (int x = 1; x <= m; x++) {
info[v][x][0] = MP[get(info[2 * v][x][0])];
info[v][x][1] = MP[get(info[2 * v + 1][x][1] + SZ1)];
}
}
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];
}
}
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() {
int SZ = 0;
for (int i = 1; i <= m; i++) {
SZ = max(SZ, info[1][i][0]);
SZ = max(SZ, info[1][i][1]);
}
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];
}
}
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: 3668kb
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: 3652kb
input:
1 1 1 0 0 0
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3748kb
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: 3616kb
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: 3756kb
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: 0ms
memory: 3668kb
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: 3676kb
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: 3664kb
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: 3596kb
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: 3600kb
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: 3728kb
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: 3656kb
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: 3680kb
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: 3712kb
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: 3776kb
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: 3752kb
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: 3620kb
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: 3652kb
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: 3644kb
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: 3772kb
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: 3780kb
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: 3700kb
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: 3948kb
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: 1ms
memory: 3972kb
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: 3880kb
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: 3816kb
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: 3880kb
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: 0
Accepted
time: 0ms
memory: 3840kb
input:
50 50 50 11111100101101000110101010001000000011101011111100 00000001110000100011100001111011000001010001001101 01101100011010111000011100000010001101110001011110 11101111110000000001101011101101000011010110111110 00000001100001101001111101101010101000111000111111 101110111011110001101101001011110111...
output:
343 344 344 342 340 339 340 341 342 341 342 342 339 339 338 340 339 339 340 342 342 342 342 341 341 340 338 337 338 337 335 332 335 336 335 335 335 337 333 333 335 334 333 333 333 334 334 333 331 331
result:
ok 50 numbers
Test #29:
score: 0
Accepted
time: 1ms
memory: 3872kb
input:
50 50 50 10110101001110100000100111111001100110101101011000 01111010100110010101110100010011001111111101100000 00111101011101011000001010010101110111000101100001 01001000110000010001010110000000001110110100100001 00110000100111001010011001100000011100110011001001 010101010000101001010110101110111010...
output:
363 363 362 361 361 363 363 363 363 364 364 364 364 363 364 367 367 367 366 366 366 366 366 364 364 364 363 363 363 361 362 361 361 362 364 366 367 367 366 364 363 362 364 365 365 365 365 362 363 362
result:
ok 50 numbers
Test #30:
score: 0
Accepted
time: 1ms
memory: 3888kb
input:
50 50 50 00010001110001000111000110000011011101011101100010 00011010011111001000100110111001010000101100001110 11010001001111010111011001000111000100001010111111 01101111100111001100001001110001101100010110001101 01111011101111000111101001101100011101101100100011 110100000110010010000001101010100110...
output:
340 340 343 342 342 342 343 342 342 340 340 341 341 342 342 341 341 341 340 341 340 340 340 340 339 341 342 341 341 341 340 340 339 338 339 338 338 338 337 338 339 339 339 338 339 340 340 340 342 342
result:
ok 50 numbers
Test #31:
score: 0
Accepted
time: 1ms
memory: 3900kb
input:
50 50 50 10010101010010110011001001110011110000000101001000 00000011001001111010010010110001101010100000101011 00100000011011011000001010010101001010110100000000 11001010000011001110000010011110110001001101010111 00001000001000000010110000111111001010100101110100 000111011000101010111011110110111110...
output:
345 344 344 343 342 343 343 344 343 344 343 344 345 348 348 349 348 351 351 351 351 352 353 351 351 349 348 352 351 352 352 353 352 351 350 348 347 347 345 345 346 345 345 346 346 345 347 347 344 345
result:
ok 50 numbers
Test #32:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
50 50 50 00010100101000100000101011110101100101110011101100 00100111010000001110011100111011111101011010101101 11011110110010010000100111011001101011100000110000 10001011011100000000100111001000101110001011110000 00110000100110110010000001110001000111111100110110 100101101111101110011011111011010110...
output:
366 362 362 363 363 364 363 364 364 360 361 361 361 361 361 361 361 360 360 360 359 358 357 356 356 356 356 355 354 355 353 351 349 350 348 348 349 348 347 349 349 349 350 351 350 350 351 352 352 353
result:
ok 50 numbers
Test #33:
score: -100
Runtime Error
input:
100 100 100 0000010000111011110000111110110100111010110110001000001110000001100111100100110101101110101010001011 1111011001001111001101101101101011000110111100100011100011110010000001110101011000010011110110101001 11000110011101000111011000010010000001101000100100111110011101101101011001000100101010...