QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227183#7190. ChessboardPPP#RE 1ms3972kbC++173.7kb2023-10-27 01:04:022023-10-27 01:04:03

Judging History

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

  • [2023-10-27 01:04:03]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3972kb
  • [2023-10-27 01:04:02]
  • 提交

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...

output:


result: