| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1233662 | msrivera1404 | Mosaic (IOI24_mosaic) | C++20 | 0 ms | 0 KiB |
#include "mosaic.h"
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm> // Para std::min y std::max
long long get_range_sum(const std::vector<long long> &pref_sum_array, int strt_idx, int end_idx){
if(strt_idx>end_idx){
return 0;
}
return pref_sum_array[end_idx +1]-pref_sum_array[strt_idx];
}
std::vector<long long> 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) {
int Q = (int)T.size();
int N = (int)X.size();
std::vector<int> fila1(N);
std::vector<int> columna1(N);
std::vector<int> fila2(N);
std::vector<int> columna2(N);
std::vector<int> capa2_lineal;
fila1[0] = Y[1];
for(int j = 1; j < N; ++j){
unsigned short up = X[j];
unsigned short left = fila1[j-1];
if(up == 0 && left == 0){
fila1[j] = 1;
} else {
fila1[j] = 0;
}
}
columna1[1] = fila1[1];
for(int i = 2; i < N; ++i){
unsigned short up = columna1[i-1];
unsigned short left = Y[i];
if(up == 0 && left == 0){
columna1[i] = 1;
} else {
columna1[i] = 0;
}
}
fila2[0] = Y[2];
for(int j = 1; j < N; ++j){
unsigned short up = fila1[j];
unsigned short left;
if(j == 1){
left = Y[2];
} else {
left = fila2[j-1];
}
if(up == 0 && left == 0){
fila2[j] = 1;
} else {
fila2[j] = 0;
}
}
columna2[0]=Y[2];
columna2[1]=fila1[2];
columna2[2] = fila2[2];
for(int i = 3; i < N; ++i){
unsigned short up = columna2[i-1];
unsigned short left = columna1[i];
if(up == 0 && left == 0){
columna2[i] = 1;
} else {
columna2[i] = 0;
}
}
if(N>=3){
for(int j=2;j<N; ++j){
capa2_lineal.push_back(fila2[j]);
}
for(int i=3; i<N; ++i){
capa2_lineal.push_back(columna2[i]);
}
}
std::vector<long long> pref_sum_X(N + 1, 0);
std::partial_sum(X.begin(), X.end(), pref_sum_X.begin() + 1);
std::vector<long long> pref_sum_Y(N + 1, 0);
std::partial_sum(Y.begin(), Y.end(), pref_sum_Y.begin() + 1);
std::vector<long long> pref_sum_F1(N + 1, 0);
std::partial_sum(fila1.begin(), fila1.end(), pref_sum_F1.begin() + 1);
std::vector<long long> pref_sum_C1(N + 1, 0);
std::partial_sum(columna1.begin(), columna1.end(), pref_sum_C1.begin() + 1);
std::vector<long long> pref_sum_F2(N + 1, 0);
std::partial_sum(fila2.begin(), fila2.end(), pref_sum_F2.begin() + 1);
std::vector<long long> pref_sum_C2(N + 1, 0);
std::partial_sum(columna2.begin(), columna2.end(), pref_sum_C2.begin() + 1);
std::vector <long long> pref_sum_CAP2(capa2_lineal.size()+1, 0);
std::partial_sum(capa2_lineal.begin(), capa2_linea.end(), pref_sum_CAP2.begin()+1);
auto get_cell_value = [&](int i, int j) -> int {
if (i < 0 || j < 0 || i >= N || j >= N) return 0;
if (i == 0) return X[j];
if (j == 0) return Y[i];
if (i == 1) return fila1[j];
if (j == 1) return columna1[i];
if (i < 2 && j < 2) { // Casillas (0,0), (0,1), (1,0), (1,1)
if (i == 0) return X[j];
else /* i == 1 */ return fila1[j];
} else if (i < 2) { // Filas 0 o 1, y columnas >= 2
if (i == 0) return X[j];
else return fila1[j];
} else if (j < 2) {
if (j == 0) return Y[i];
else return columna1[i];
} else if (i == 2 || j == 2) { // (Capa 2)
if (i == 2) return fila2[j];
else return columna2[i];
} else { // Región interior (i >= 3 y j >= 3)
int k_offset = std::min(i, j) - 2;
if (i <= j) { // Proyecta en fila 2
return fila2[j - k_offset];
} else { // Proyecta en columna 2
return columna2[i - k_offset];
}
}
};
std::vector<long long> respuestas(Q);
for(int k = 0; k < Q; ++k){
int r1=T[k];
int r2=B[k];
int c1=L[k];
int c2=R[k];
if (r1 == r2 && c1 == c2) {
respuestas[k] = get_cell_value(r1, c1);
continue;
}
long long current_blacks=0;
int r_cut=2;
int c_cut=2;
int r1_r1=r1;
int r2_r1=std::min(r2,r_cut-1);
int c1_r1=c1;
int c2_r1=std::min(c2, c_cut-1);
if(r1_r1<=r2_r1 && c1_r1<=c2_r1){
for(int i=r1_r1; i<=r2_r1;++i){
for(int j=c1_r1; j<=c2_r1;++j){
current_blacks+=get_cell_value(i,j);
}
}
}
int r1_r2=r1;
int r2_r2=std::min(r2, r_cut-1);
int c1_r2=std::max(c1,c_cut);
int c2_r2=c2;
if(r1_r2<=r2_r2 && c1_r2<=c2_r2){
if(r1_r2<=0 && r2_r2>=0){
current_blacks+=get_range_sum(pref_sum_X, c1_r2, c2_r2);
}
if(r1_r2<=1 && r2_r2>=1){
current_blacks+=get_range_sum(pref_sum_F1, c1_r2, c2_r2);
}
}
int r1_r3=std::max(r1, r_cut);
int r2_r3=r2;
int c1_r3=c1;
int c2_r3=std::min(c2, c_cut-1);
if(r1_r3<=r2_r3 && c1_r3<=c2_r3){
if(c1_r3<=0 && c2_r3>=0){
current_blacks+=get_range_sum(pref_sum_Y, r1_r3, r2_r3);
}
if(c1_r3<=1 && c2_r3>=1){
current_blacks+=get_range_sum(pref_sum_C1, r1_r3, r2_r3);
}
}
int r1_r4=std::max(r1, r_cut);
int r2_r4=r2;
int c1_r4=std::max(c1, c_cut);
int c2_r4=c2;
if(r1_r4<=r2_r4 && c1_r4<=c2_r4){
if(r1_r4==r2_r4){
for(int j=c1_r4; j<=c2_r4; ++j){
current_blacks+=get_cell_value(r1_r4, j);
}
}
}
respuestas[k]=current_blacks;
}
return respuestas;
}