#include <bits/stdc++.h> using namespace std; #define ll long long const ll mmod = 998244353; #define vl vector<long long> #define vll vector<vector<long long>> #define pl pair<long long, long long> #define vb vector<bool> 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){ ll n, q; n = X.size(); q = T.size(); vll row3; vll col3; vl x1, y1; for (ll i = 0; i <n; i++){ x1.push_back(X[i]); y1.push_back(Y[i]); } row3.push_back(x1); col3.push_back(y1); // Oprava: Kontrola velikosti N, aby nedošlo k přístupu mimo paměť pro N=1,2 if (n > 1) { row3.push_back({(ll)Y[1]}); } if (n > 2) { row3.push_back({(ll)Y[2]}); } if (n > 1) { col3.push_back({(ll)X[1]}); } if (n > 2) { col3.push_back({(ll)X[2]}); } for (ll i = 1; i < 3; i++){ if (i >= row3.size()) break; // Oprava: Ochrana loopu pro malé N for (ll j = 1; j < n; j++){ ll v1 = 0; ll v2 = 0; // Podmínka pro generování musí být bezpečná if (row3[i][j-1] == 0 && row3[i-1][j] == 0){ v1 = 1; } if (col3[i][j-1] == 0 && col3[i-1][j] == 0){ v2 = 1; } row3[i].push_back(v1); col3[i].push_back(v2); } } vl s1, s2, s3; // Flattening s1 (Layer 0) for (ll i = n-1; i>=0; i--){ s1.push_back(col3[0][i]); } for (ll i = 1; i < n; i++){ s1.push_back(row3[0][i]); } // Flattening s2 (Layer 1) if (n > 1) { // Ochrana pro malé N for (ll i = n-1; i>=1; i--){ s2.push_back(col3[1][i]); } for (ll i = 2; i < n; i++){ s2.push_back(row3[1][i]); } } // Flattening s3 (Layer 2+) if (n > 2) { // Ochrana pro malé N for (ll i = n-1; i>=2; i--){ s3.push_back(col3[2][i]); } for (ll i = 3; i < n; i++){ s3.push_back(row3[2][i]); } } vl p1, p2, p3; p1 = p2 = p3 = {0}; for (ll i = 0; i < s1.size(); i++){ p1.push_back(s1[i] + p1[i]); } for (ll i = 0; i < s2.size(); i++){ p2.push_back(s2[i] + p2[i]); } for (ll i = 0; i < s3.size(); i++){ p3.push_back(s3[i] + p3[i]); } // Oprava: Odstraněno q2. q1 nyní slouží pro vážený součet (S[i] * (i+1)) vl q1; q1 = {0}; for (ll i = 0; i < s3.size(); i++){ q1.push_back(q1[i] + s3[i]*(i+1)); } vl ans; for (ll i = 0; i < q; i++){ ll l, r, u, d; l = L[i]; r = R[i]; u = T[i]; d = B[i]; ll a, b; ll suma = 0; //Layer1 (Index 0) b = 0; a = 1e9; if (l == 0){ a = min(a, n-d-1); b = max(b, n-u); } if (u == 0){ a = min(a, n + l - 1); b = max(b, n + r); } if (a < b){ suma += p1[b] - p1[a]; } //Layer2 (Index 1) b = 0; a = 1e9; if (l <= 1 && r >= 1){ a = min(a, n-d-1); b = max(b, n-max(u,1ll)); } if (u <= 1 && d >= 1){ a = min(a, n + max(l,1ll) - 3); b = max(b, n + r - 2); } if (a < b && s2.size() > 0){ // check if s2 exists // Ochrana bounds, protože s2 může být prázdné nebo kratší a = max(0ll, a); b = min((ll)p2.size()-1, b); if(a < b) suma += p2[b] - p2[a]; } // Layer3 (Recursive) if (r >= 2 && d >= 2 && s3.size() > 0){ ll l_curr = max(2ll, l); ll u_curr = max(2ll, u); // Zde a, b jsou indexy do s3 ll a = l_curr - 2 + (n-1)-d; ll b = r - 2 + n - u_curr; // b je zde v logice kódu spíše 'poslední index', ale pro prefix sumy potřebujeme 'exclusive end'. // V původním kódu jste používali p3[b] - p3[b-t], což naznačuje, že 'b' v array logice je exclusive bound (index + 1). // Původní výpočet: b = r - 2 + n - u. // Max diagonála je r - u. Index v s3 je (r-u) + n - 3. // Vaše b = (r-u) + n - 2. To odpovídá (Index_max + 1). Takže b je správně exclusive upper bound. ll t = min(d-u_curr, r-l_curr); // thickness (počet kroků náběhu) // Rising slope: Sum S[i]*(dist_from_start) // Sum_{k=0 to t-1} S[a+k]*(k+1) = (Q1[a+t] - Q1[a]) - a*(P3[a+t] - P3[a]) suma += q1[a+t] - q1[a]; suma -= (p3[a+t] - p3[a])*a; // Constant plateau: Sum S[i]*(t+1) // Range [a+t, b-t) (exclusive end) if (a+t < b-t) { suma += (p3[b-t] - p3[a+t])*(t+1); } // Falling slope: Sum S[i]*(dist_from_end) // Range [b-t, b). Váhy t, t-1, ..., 1. // Vzorec: (b+1)*Sum(S) - Sum(S*i) // = (b+1)*(P3[b] - P3[b-t]) - (Q1[b] - Q1[b-t]) // Oprava: Nahrazení chybné q2 logiky tímto vzorcem suma += (b+1)*(p3[b] - p3[b-t]); suma -= (q1[b] - q1[b-t]); } ans.push_back(suma); } return ans; } /*/int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); // Test case vector<int> X {1, 0, 1, 0, 1}; vector<int> Y {1, 1, 0, 1, 0}; vector<int> T {1}; vector<int> B {3}; vector<int> L {1}; vector<int> R {3}; // Expected based on manual trace or constraints vl ans = mosaic(X, Y, T, B, L, R); for (auto x : ans){ cout << x << "\n"; } return 0; } /*/