#include "mosaic.h"
#include <iostream>
#include <numeric>
#include <vector>
#include <algorithm>
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();
//RESUELVE SUBTAREA 1 Y 2
// std::vector <std::vector <int>> mosaico(N, std::vector<int>(N));
// for(int j=0; j<N;++j){
// mosaico[0][j]=X[j];
// }
// for(int i=0;i<N;++i){
// mosaico[i][0]=Y[i];
// }
// for(int i=1; i<N; ++i){
// for(int j=1;j<N;++j){
// if(mosaico[i-1][j]==0 && mosaico[i][j-1]==0){
// mosaico[i][j]=1;
// }
// else{
// mosaico[i][j]=0;
// }
// }
// }
// std::vector <long long> respuestas(Q);
// for(int k=0; k<Q; ++k){
// long long current_blacks=0;
// int r1=T[k];
// int r2=B[k];
// int c1=L[k];
// int c2=R[k];
// for(int i=r1; i<=r2; ++i){
// for(int j=c1; j<=c2; ++j){
// if(mosaico[i][j]==1){
// current_blacks++;
// }
// }
// }
// respuestas[k]=current_blacks;
// }
// return respuestas;
//RESUELVE SUBTAREA 3
// std::vector <long long> respuestas(Q);
// std::vector <long long> prefix_sums(N+1,0);
// std::partial_sum(X.begin(), X.end(), prefix_sums.begin()+1);
// for(int k=0; k<Q; ++k){
// long long current_blacks=0;
// int r1=T[k];
// int c1=L[k];
// int c2=R[k];
// current_blacks=prefix_sums[c2+1]-prefix_sums[c1];
// respuestas[k]=current_blacks;
// }
// return respuestas;
//RESUELVE SUBTAREA 1,2,4
std::vector <std::vector <int>> mosaico(N, std::vector<int>(N));
for(int j=0; j<N;++j){
mosaico[0][j]=X[j];
}
for(int i=0;i<N;++i){
mosaico[i][0]=Y[i];
}
for(int i=1; i<N; ++i){
for(int j=1;j<N;++j){
if(mosaico[i-1][j]==0 && mosaico[i][j-1]==0){
mosaico[i][j]=1;
}
else{
mosaico[i][j]=0;
}
}
}
std::vector <long long> respuestas(Q);
std::vector<std::vector<long long>> pref_sum_2D(N+1, std::vector <long long> (N+1,0));
for(int i=0; i<N; ++i){
std::partial_sum(mosaico[i].begin(), mosaico[i].end(), pref_sum_2D[i+1].begin()+1);
}
for(int j=1; j<=N; ++j){
for(int i=1; i<=N;++i){
pref_sum_2D[i][j]+=pref_sum_2D[i-1][j];
}
}
for(int k=0; k<Q;++k){
int r1=T[k]; int r2=B[k];
int c1=L[k]; int c2=R[k];
long long current_blacks=pref_sum_2D[r2+1][c2+1]-pref_sum_2D[r1][c2+1]-pref_sum_2D[r2+1][c1]+pref_sum_2D[r1][c1];
respuestas[k]=current_blacks;
}
return respuestas;
// //RESUELVE SUBTAREA 5
// 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];
// long long current_blacks=0;
// int effective_r1=std::max(r1,1);
// int effective_c1=std::max(c1,1);
// long long checkboard_rows=std::max(0,r2-effective_r1+1);
// long long checkboard_cols=std::max(0,c2-effective_c1+1);
// long long checkboard_area=checkboard_rows*checkboard_cols;
// current_blacks=checkboard_area/2;
// if(checkboard_area%2!=0){
// if((effective_r1+effective_c1)%2==0){
// current_blacks++;
// }
// }
// respuestas[k]=current_blacks;
// }
// return respuestas;
}
