QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#832824	#9240. Mosaic	le0n^#	5	42ms	27416kb	C++20	3.0kb	2024-12-26 09:00:59	2024-12-26 09:01:00

Judging History

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

[2024-12-26 09:01:00]
评测

测评结果：5
用时：42ms
内存：27416kb

查看

[2024-12-26 09:00:59]
提交

answer

#include "mosaic.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 2e5 + 5;
struct BIT
{
    ll tree[N];
    int n;
    void init(int m)
    {
        n = m;
        int i;
        for(i = 1; i <= n; i++)
            tree[i] = 0;
    }
    void add(int x, ll y)
    {
        while(x <= n)
        {
            tree[x] += y;
            x += (x & -x);
        }
    }
    ll qry(int x)
    {
        ll ans = 0;
        while(x)
        {
            ans += tree[x];
            x -= (x & -x);
        }
        return ans;
    }
    ll qlr(int l, int r)
    {
        l = max(l, 1);
        r = min(r, n);
        if(l > r)
            return 0;
        return qry(r) - qry(l - 1);
    }
};
BIT qwq[4];
int row[4][N], col[N][4], sr[4][N], sc[4][N], n;
ll sum(int x, int y)
{
    if(x < 0 || y < 0)
        return 0;
    if(x < 3)
        return sr[x][y];
    if(y < 3)
        return sc[x][y];
    ll res = sr[2][y] + sc[x][2] - sr[2][2], a;
    if(row[2][2])
        res += min(x - 2, y - 2);
    a = y - x + 2;
    res += qwq[0].qlr(1, a) * (x - 2) + qwq[0].qlr(a + 1, n) * y - qwq[1].qlr(a + 1, n);
    a = x - y + 2;
    res += qwq[2].qlr(1, a) * (y - 2) + qwq[2].qlr(a + 1, n) * x - qwq[3].qlr(a + 1, n);
    return res;
}
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R)
{
    n = X.size();
    int q = T.size(), i, j;
    vector<ll> C(q, 0);
    for(i = 0; i < n; i++)
        row[0][i] = X[i];
    for(i = 0; i < n; i++)
        col[i][0] = Y[i];
    for(i = 0; i < 3; i++)
    {
        row[i][0] = col[i][0];
        col[0][i] = row[0][i];
    }
    for(i = 1; i < 3; i++)
        for(j = 1; j < n; j++)
            row[i][j] = (!row[i - 1][j] && !row[i][j - 1]);
    for(i = 1; i < n; i++)
        for(j = 1; j < 3; j++)
            col[i][j] = (!col[i - 1][j] && !col[i][j - 1]);
    for(i = 0; i < 3; i++)
        for(j = 0; j < n; j++)
            sr[i][j] = row[i][j];
    for(i = 0; i < 3; i++)
        for(j = 1; j < n; j++)
            sr[i][j] += sr[i][j - 1];
    for(i = 1; i < 3; i++)
        for(j = 0; j < n; j++)
            sr[i][j] += sr[i - 1][j];
    for(i = 0; i < n; i++)
        for(j = 0; j < 3; j++)
            sc[i][j] = col[i][j];
    for(i = 0; i < n; i++)
        for(j = 1; j < 3; j++)
            sc[i][j] += sc[i][j - 1];
    for(i = 1; i < n; i++)
        for(j = 0; j < 3; j++)
            sc[i][j] += sc[i - 1][j];
    for(i = 0; i < 4; i++)
        qwq[i].init(n);
    for(i = 3; i < n; i++)
        if(row[2][i])
        {
            qwq[0].add(i, 1);
            qwq[1].add(i, i);
        }
    for(i = 3; i < n; i++)
        if(col[i][2])
        {
            qwq[2].add(i, 1);
            qwq[3].add(i, i);
        }
    for(i = 0; i < q; i++)
        C[i] = sum(B[i], R[i]) - sum(T[i] - 1, R[i]) - sum(B[i], L[i] - 1) + sum(T[i] - 1, L[i] - 1);
    return C;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 0ms

memory: 20188kb

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: 20180kb

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: 2ms

memory: 20200kb

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: 20276kb

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: 1ms

memory: 16112kb

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: 3ms

memory: 16392kb

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: 20164kb

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: 3ms

memory: 18164kb

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: 16088kb

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: 16084kb

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

Runtime Error

Dependency #1:

100%

Accepted

Test #11:

score: 0

Runtime Error

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:

result:

Subtask #3:

score: 0

Runtime Error

Test #18:

score: 0

Runtime Error

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:

result:

Subtask #4:

score: 0

Skipped

Dependency #2:

Subtask #5:

score: 0

Wrong Answer

Test #31:

score: 0

Wrong Answer

time: 42ms

memory: 27416kb

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
11
2
5
0
4
7
2
1
6
5
0
0
1
11
4
3
14
6
1
5
5
2
3
6
8
5
8
3
7
3
10
1
6
3
3
9
0
2
6
5
12
11
0
3
3
1
6
3
2
9
2
4
10
0
2
5
2
2
1
2
4
2
4
2
10
20
9
0
7
4
2
8
8
2
4
1
4
4
1
12
7
6
4
1
2
3
11
1
2
2
2
9
11
11
2
0
3
1
2
8
12
3
1
5
0
7
8
4
21
2
2
4
6
5
6
2
8
4
12
2
6
3
5
1
...

result:

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

Subtask #6:

score: 0

Runtime Error

Test #42:

score: 0

Runtime Error

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:

result:

Subtask #7:

score: 0

Skipped

Dependency #3:

Subtask #8:

score: 0

Skipped

Dependency #1:

100%

Accepted