QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#553206	#9240. Mosaic	Hunster^#	5	69ms	36168kb	C++20	2.3kb	2024-09-08 10:41:04	2024-09-08 10:41:04

Judging History

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

[2024-09-08 10:41:04]
评测

测评结果：5
用时：69ms
内存：36168kb

查看

[2024-09-08 10:41:04]
提交

answer

#include <bits/stdc++.h>

using LL = long long;

constexpr int N = 200005, W = 10;

int n, q, h0[W][N], h1[N][W];
LL a[2 * N], b[2 * N];

std::vector<LL> mosaic(
    std::vector<int> X, std::vector<int> Y,
    std::vector<int> T, std::vector<int> B,
    std::vector<int> L, std::vector<int> R
) {
    n = X.size();
    q = T.size();
    std::vector<LL> ans(q);
    if (n < W) {
        std::vector<std::vector<int>> h(n, std::vector<int>(n));
        for (int i = 0; i < n; i++) {
            h[0][i] = X[i];
            h[i][0] = Y[i];
        }
        for (int i = 1; i < n; i++) for (int j = 1; j < n; j++) h[i][j] = !(h[i - 1][j] | h[i][j - 1]);
        for (int i = 0; i < q; i++) {
            for (int x = T[i]; x <= B[i]; x++) for (int y = L[i]; y <= R[i]; y++)
                ans[i] += h[x][y];
        }
    }
    else {
        for (int i = 0; i < n; i++) {
            h0[0][i] = X[i];
            h1[i][0] = Y[i];
        }
        for (int i = 1; i < W; i++) {
            h0[i][0] = Y[i];
            h1[0][i] = X[i];
            for (int j = 1; j < n; j++) {
                h0[i][j] = !(h0[i - 1][j] | h0[i][j - 1]);
                h1[j][i] = !(h1[j - 1][i] | h1[j][i - 1]);
            }
        }
        for (int i = W - 1, j = W - 1; j < n; j++) a[j - i + N] += h0[i][j];
        for (int j = W - 1, i = W; i < n; i++) a[j - i + N] += h1[i][j];
        for (int i = 1; i < 2 * N; i++) {
            a[i] += a[i - 1];
            b[i] = b[i - 1] + a[i];
        }
        const auto calc = [&](int x, int y, int len) { return (b[y + len - 1] - b[y - 1]) - (b[x + len - 1] - b[x - 1]); };
        for (int i = 0; i < q; i++) {
            int x = T[i] - B[i] + 1, y = R[i] - L[i] + 1;
            if (x <= y) {
                ans[i] += calc(L[i] - B[i] + N, L[i] - T[i] + N, x - 1);
                ans[i] += calc((R[i] - (x - 1)) - B[i] + N, R[i] - B[i] + N, x - 1);
                ans[i] += calc(L[i] - B[i] + N - 1, (R[i] - (x - 1)) - B[i] + N, y);
            }
            else {
                ans[i] += calc(L[i] - (B[i] + (y - 1)) + N, L[i] - T[i] + N, y - 1);
                ans[i] += calc(L[i] - B[i] + N, R[i] - B[i] + N, y - 1);
                ans[i] += calc(L[i] - B[i] + N - 1, R[i] - (B[i] - (y - 1)) + N, x);
            }
        }
    }
    return ans;
}
/*
1010
1001
0100
1010
*/

源文件, 语言: C++20

详细

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 0ms

memory: 3812kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
1
0
0
10
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
0
0
0
0
0
0
0
0
0
0

result:

ok

Test #2:

score: 5

Accepted

time: 0ms

memory: 3800kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
1
1
1
10
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
1
1
1
1
1
1
1
1
1
1

result:

ok

Test #3:

score: 5

Accepted

time: 0ms

memory: 3804kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
2
1 0
1 0
10
1 1 0 1
1 1 0 1
0 0 0 0
0 1 0 1
0 1 0 1
1 1 0 0
0 1 0 1
0 1 1 1
1 1 0 1
0 0 0 1

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
1
1
1
2
2
0
2
1
1
1

result:

ok

Test #4:

score: 5

Accepted

time: 0ms

memory: 3816kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
2
1 0
1 0
10
0 1 1 1
0 1 0 1
0 1 0 0
1 1 0 1
0 1 0 1
0 1 0 0
1 1 1 1
0 0 0 1
0 1 0 0
1 1 0 0

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
1
2
1
1
2
1
1
1
1
0

result:

ok

Test #5:

score: 5

Accepted

time: 0ms

memory: 3888kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
2
0 1
0 0
10
0 1 0 0
0 0 0 1
0 1 0 0
0 0 0 0
1 1 1 1
0 1 0 0
0 0 0 1
0 1 0 1
0 1 0 1
0 1 0 1

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
0
1
0
0
0
0
1
1
1
1

result:

ok

Test #6:

score: 5

Accepted

time: 0ms

memory: 3808kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
2
1 1
1 0
10
0 0 0 1
0 0 0 1
1 1 0 1
0 1 0 1
0 1 0 0
0 1 1 1
1 1 0 1
0 0 1 1
0 1 0 0
0 1 0 0

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
2
2
0
2
1
1
0
1
1
1

result:

ok

Test #7:

score: 5

Accepted

time: 0ms

memory: 4100kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
2
0 0
0 1
10
0 0 0 0
0 1 0 1
0 1 0 1
0 1 0 1
0 1 1 1
0 0 1 1
0 0 0 1
0 1 0 0
1 1 0 1
1 1 0 1

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
0
1
1
1
0
0
0
1
1
1

result:

ok

Test #8:

score: 5

Accepted

time: 0ms

memory: 3812kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
2
1 0
1 1
10
0 1 0 0
1 1 0 1
0 0 0 1
1 1 1 1
1 1 0 0
0 1 1 1
0 1 0 0
0 0 1 1
1 1 0 1
0 1 0 1

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
2
1
1
0
1
0
2
0
1
2

result:

ok

Test #9:

score: 5

Accepted

time: 0ms

memory: 3752kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
2
0 1
0 1
10
0 1 0 1
0 1 0 1
1 1 1 1
0 1 0 1
0 0 1 1
0 1 0 1
0 1 1 1
0 0 0 0
0 1 0 0
0 1 0 1

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
2
2
0
2
1
2
1
0
1
2

result:

ok

Test #10:

score: 5

Accepted

time: 0ms

memory: 4032kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
2
1 1
1 1
10
0 0 0 1
0 1 0 0
0 1 0 0
0 1 0 1
0 0 0 0
0 1 0 1
0 1 0 1
0 1 1 1
0 1 0 1
1 1 1 1

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
2
2
2
3
1
3
3
1
3
0

result:

ok

Subtask #2:

score: 0

Wrong Answer

Dependency #1:

100%

Accepted

Test #11:

score: 0

Wrong Answer

time: 0ms

memory: 18820kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
199
0 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 1 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 0 0 0 1...

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
1926
8997
2119
1007
19956
2271
2925
14816
1017
2692
83
1598
3538
9822
9315
1494
3521
14
268
3584
6212
88
9021
138
1958
1617
172
5233
4503
10497
8414
6271
95
7053
1626
7702
6869
3917
776
8419
514
2514
667
1784
1163
11316
3196
3056
329
5792
15323
9993
1288
5478
3708...

result:

wrong answer 3rd lines differ - on the 1st token, expected: '1078', found: '1926'

Subtask #3:

score: 0

Wrong Answer

Test #18:

score: 0

Wrong Answer

time: 69ms

memory: 36016kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
199999
0 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 0 0 ...

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
3117878
-57348961630
-38974358172
-50821444479
-38908953890
-54243544812
791804981
-35190388548
372431938
344566349
-45276001529
-53995112702
316973706
1016181403
2441419872
-49535413134
-45759668856
-41200799725
-53817869099
3098347708
-42375012306
3475656
-51322...

result:

wrong answer 3rd lines differ - on the 1st token, expected: '1314', found: '3117878'

Subtask #4:

score: 0

Skipped

Dependency #2:

Subtask #5:

score: 0

Wrong Answer

Test #31:

score: 0

Wrong Answer

time: 35ms

memory: 27320kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
200000
1 7 0 4
3 4 3 4
3 6 2 5
4 5 6 7
5 7 2 8
0 6 4 7
0 5 6 7
1 3 9 9
6 9 1 7
2 9 4 6
4 4 6 7
0 1 8 8
7 7 0 3
0 4 1 7
2 2 0 9
3 9 4 6
3 9 0 9
1 8 4 6
4 5 5 7
0 6 2 3
2 3 0 6
1 9 8 8
2 4 3 4
3 6 2 9
3 9 2 7
1 3 0 3
0 8 2 4
3...

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
8
3
6
0
7
4
-1
0
8
5
0
0
0
4
3
5
16
5
0
3
4
1
3
5
10
6
5
4
2
5
7
1
5
5
6
8
-1
5
6
1
10
12
0
1
5
3
7
0
1
5
2
3
9
0
0
0
2
1
1
7
1
1
5
1
9
15
7
1
1
3
1
5
-2
0
2
0
8
5
6
9
4
5
3
1
4
3
12
0
4
1
3
6
8
3
7
1
0
1
1
7
3
3
1
7
0
8
7
2
14
6
1
0
3
-2
6
1
3
-1
7
3
5
3
4
0
4
4
...

result:

wrong answer 3rd lines differ - on the 1st token, expected: '14', found: '8'

Subtask #6:

score: 0

Wrong Answer

Test #42:

score: 22

Accepted

time: 68ms

memory: 36168kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
199999
0 1 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 0 0 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 0 0 1 0 1 ...

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
0
1
0
1
0
1
0
0
1
1
1
1
0
1
0
1
1
1
0
0
1
1
1
0
0
1
0
0
0
1
0
0
1
0
1
0
1
1
1
1
1
0
1
0
0
0
0
1
1
0
1
0
0
0
1
0
0
0
0
1
0
1
0
0
0
0
1
0
0
0
0
1
0
1
0
1
0
0
0
1
0
0
1
0
0
0
0
0
1
0
1
0
0
1
0
1
1
0
1
1
1
1
1
0
0
1
0
0
1
0
0
1
0
0
0
0
0
1
1
1
0
1
1
1
0
1
0
1
0
1
0
1
...

result:

ok

Test #43:

score: 22

Accepted

time: 64ms

memory: 35960kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
200000
1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 1 1 0 0 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 1 0 1 1 1 0 1 0 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 1 1 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0 0 1 0 1 ...

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
1
1
0
1
0
1
1
0
1
0
1
0
0
1
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1
1
0
1
1
0
1
0
0
0
0
1
1
0
0
0
0
0
1
1
0
1
1
1
1
1
1
1
1
1
0
1
0
0
1
0
1
0
0
1
1
1
1
1
0
0
0
0
1
0
1
1
0
0
1
0
0
0
1
1
1
0
1
1
1
1
1
0
1
1
0
0
1
1
0
0
0
1
0
1
0
0
1
0
0
0
0
0
0
1
0
1
...

result:

ok

Test #44:

score: 0

Wrong Answer

time: 65ms

memory: 36048kb

input:

njJ9Z7VxxKGR6SUcJMgdzy3qMz4JZ1Tq
200000
1 0 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 0 0 1 0 1 1 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 ...

output:

Wm5rkGNobnYjFI7TIY17RAm6FAQ2LlO9
OK
0
1
1
0
1
0
0
1
0
0
1
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
1
1
0
0
0
0
0
0
0
1
1
1
1
0
1
1
1
0
0
0
0
0
0
1
1
0
0
1
0
1
1
0
1
0
0
0
0
0
0
0
0
0
1
0
1
0
1
1
0
1
1
0
0
0
1
0
1
0
1
1
1
1
0
0
1
1
1
0
1
0
1
0
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
0
1
1
0
0
1
1
...

result:

wrong answer 46th lines differ - on the 1st token, expected: '0', found: '1'

Subtask #7:

score: 0

Skipped

Dependency #3:

Subtask #8:

score: 0

Skipped

Dependency #1:

100%

Accepted