#include "mosaic.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){
int N = X.size(), Q = T.size();
if (N < 4){
vector<vector<int>> bruh(N, vector<int>(N));
bruh[0] = X;
for (int i=1; i<N; i++) bruh[i][0] = Y[i];
for (int i=1; i<N; i++){
for (int j=1; j<N; j++) bruh[i][j] = 1-(bruh[i-1][j] | bruh[i][j-1]);
}
vector<ll> res(Q, 0);
for (int k=0; k<Q; k++){
for (int i=T[k]; i<=B[k]; i++){
for (int j=L[k]; j<=R[k]; j++) res[k] += bruh[i][j];
}
}
return res;
}
vector<vector<int>> h(3, vector<int>(N)), v(3, vector<int>(N));
h[0] = X;
v[0] = Y;
for (int i=1; i<3; i++){
h[i][0] = Y[i];
v[i][0] = X[i];
}
for (int i=1; i<3; i++){
for (int j=1; j<N; j++){
h[i][j] = 1-(h[i-1][j] | h[i][j-1]);
v[i][j] = 1-(v[i-1][j] | v[i][j-1]);
}
}
vector<ll> z;
for (int i=N-1; i>=2; i--) z.push_back(v[2][i]);
for (int i=3; i<N; i++) z.push_back(h[2][i]);
vector<vector<ll>> psh(3, vector<ll>(N+1, 0)), psv(3, vector<ll>(N+1, 0));
for (int i=0; i<3; i++){
for (int j=0; j<N; j++){
psh[i][j+1] = psh[i][j]+h[i][j];
psv[i][j+1] = psv[i][j]+v[i][j];
}
}
int s = 2*N-5;
vector<ll> psz(s+1, 0), zx(s+1), xz(s+1);
for (int i=0; i<s; i++){
psz[i+1] = psz[i]+z[i];
zx[i+1] = zx[i]+z[i]*(ll)(i+1);
xz[i+1] = xz[i]+z[i]*(ll)(s-i);
}
vector<ll> res(Q, 0);
for (int i=0; i<Q; i++){
for (int j=T[i]; j<=min(B[i], 2); j++) res[i] += psh[j][R[i]+1]-psh[j][L[i]];
if (B[i] >= 3){
for (int j=L[i]; j<=min(R[i], 2); j++) res[i] += psv[j][B[i]+1]-psv[j][max(T[i], 3)];
}
if (B[i] < 3 || R[i] < 3) continue;
int a = max(3, L[i])-B[i]+(N-3), b = max(3, L[i])-max(3, T[i])+(N-3), c = R[i]-B[i]+(N-3), d = R[i]-max(3, T[i])+(N-3);
if (b > c) swap(b, c);
//cout << a << " " << b << " " << c << " " << d << endl;
res[i] += zx[b]-zx[a]-(psz[b]-psz[a])*(ll)a + xz[d+1]-xz[c+1]-(psz[d+1]-psz[c+1])*(ll)(s-1-d) + (psz[c+1]-psz[b])*(ll)(b-a+1);
}
return res;
}
# | 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... |