| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1221521 | slimsavern | Mosaic (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include <vector>
#include <cstdint>
#include "mosaic.h"
using namespace std;
vector<int64_t> mosaic(
const vector<int>& X, const vector<int>& Y,
const vector<int>& T, const vector<int>& B,
const vector<int>& L, const vector<int>& R) {
int N = X.size(), Q = T.size();
// Use 1D flat arrays for cache efficiency
vector<int> A(N * N, 0);
vector<int64_t> S((N + 1) * (N + 1), 0);
auto idx = [&](int i, int j) { return i * N + j; };
auto sidx = [&](int i, int j) { return i * (N + 1) + j; };
// First row and column
for (int j = 0; j < N; ++j) A[idx(0, j)] = X[j];
for (int i = 0; i < N; ++i) A[idx(i, 0)] = Y[i];
// Fill in the rest of the A matrix
for (int i = 1; i < N; ++i) {
for (int j = 1; j < N; ++j) {
A[idx(i, j)] = (A[idx(i - 1, j)] == 0 && A[idx(i, j - 1)] == 0) ? 1 : 0;
}
}
// 2D prefix sum into 1D array
for (int i = 0; i < N; ++i) {
for (int j = 0; j < N; ++j) {
S[sidx(i + 1, j + 1)] = A[idx(i, j)]
+ S[sidx(i, j + 1)]
+ S[sidx(i + 1, j)]
- S[sidx(i, j)];
}
}
// Answer the queries
vector<int64_t> res(Q);
for (int k = 0; k < Q; ++k) {
int t = T[k], b = B[k], l = L[k], r = R[k];
res[k] = S[sidx(b + 1, r + 1)]
- S[sidx(t, r + 1)]
- S[sidx(b + 1, l)]
+ S[sidx(t, l)];
}
return res;
}