🔒 bitwise or problem

[dusk moat]

given 2 arrays a, b with size n, m, we construct the matrix mat, where mat[i][j] = a[i] | b[j] where | is bitwise or. there are q questions of i1, j1, i2, j2 where we have to calculate the sum of the elements from the submatrix of mat spanning from i1,j2 to i2,j2.
n,m,q <= 200.000
we have 1s and 256mb
the elements from the arrays are < 2^26

[turbid crypt]

@dusk moat

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[compact abyss]

200.000 as in 200k?
then the matrices wouldn't even fit in memory I don't think

[dusk moat]

without constructing the matrix, i have no idea how to do this. im thinking maybe partial sums. i think it's all just prebuilding arrays since an O(n) 200k times wouldn't work but i have no idea what

[compact abyss]

like what, the max is 1e10 ints in just 1 matrix?

[dusk moat]

well the problem expects you to get the sum without building the matrix, perphaps

[compact abyss]

how would that work exactly?
if you don't keep the matrices in memory, you can't even query naively
wait nvm I saw incorrectly the task statement

[dusk moat]

you can bruteforce it by just doing s += a[i] | b[i] instead of s += m[i][j]

[compact abyss]

yeah I thought a and b were both n x m matrices, whoops

[dusk moat]

3 4 2
1 4 3
4 6 1 0
1 1 3 4
1 2 3 3```

53
29```

5 7 1 1
4 6 5 4
7 7 3 3``` here is an example input, output and what the matrix would look like

[turbid crypt]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.