QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#227234#7190. ChessboardPPPWA 1ms4064kbC++174.6kb2023-10-27 04:07:152023-10-27 04:07:15

Judging History

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

  • [2023-10-27 04:07:15]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4064kb
  • [2023-10-27 04:07:15]
  • 提交

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;
}

詳細信息

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'