#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) {
int N = (int)X.size();
int Q = (int)T.size();
vector<vector<int>> grid(N, vector<int>(N));
vector<vector<ll>> preRow(N, vector<ll>(N + 1));
vector<vector<ll>> prc(N + 1, vector<ll>(N + 1));
for(int i = 0; i < N; i++){
grid[0][i] = X[i];
grid[i][0] = Y[i];
}
for(int y = 1; y < N; y++){
for(int x = 1; x < N; x++){
int color = grid[y][x - 1] == 0 && grid[y - 1][x] == 0 ? 1 : 0;
grid[y][x] = color;
}
}
for(int x = 1; x <= N; x++){
for(int y = 0; y < N; y++){
preRow[y][x] = preRow[y][x - 1] + grid[y][x - 1];
}
}
for(int y = 1; y <= N; y++){
for(int x = 1; x <= N; x++){
prc[y][x] = prc[y - 1][x] + preRow[y - 1][x];
}
}
vector<ll> r(Q);
for(int i = 0; i < Q; i++){
ll updown = prc[B[i] + 1][R[i] + 1] - prc[T[i]][L[i]];
ll left = prc[B[i] + 1][L[i]] - prc[T[i]][L[i]];
ll up = prc[T[i]][R[i] + 1] - prc[T[i]][L[i]];
r[i] = updown - left - up;
}
return r;
}
// #include "grader.cpp"
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |