Submission #1223056

#TimeUsernameProblemLanguageResultExecution timeMemory
1223056LucaIlieMosaic (IOI24_mosaic)C++20
100 / 100
98 ms28644 KiB
#include "mosaic.h" #include <bits/stdc++.h> using namespace std; const int MAX_N = 2e5; const int MAX_N2 = 5001; int matL[4][MAX_N], matC[MAX_N + 1][4]; int spL[4][MAX_N], spC[MAX_N + 1][4]; int diag[2 * MAX_N + 5]; int spD[2 * MAX_N + 5]; long long spDD[2 * MAX_N + 5]; int n; long long getImportantSumRectangle(int l1, int c1, int l2, int c2) { if (l1 > l2 || c1 > c2) return 0; int d1 = l1 - c2 + n, d2 = l2 - c1 + n; int maxx = min(l2 - l1, c2 - c1); long long ans = 0; int l = d1 - 1, r = min(d2, d1 + maxx - 1); ans += spDD[r] - spDD[l] - (long long)(spD[r] - spD[l]) * l; // for (int d = l + 1; d <= r; d++) // ans += diag[d] * (d - l); ans += (long long)(spD[d2 - maxx] - spD[d1 + maxx - 1]) * (maxx + 1); // for (int d = d1 + maxx; d <= d2 - maxx; d++) // ans += diag[d] * (maxx + 1); l = max(d2 - maxx, d1 - 1), r = d2; ans += (long long)(r - l + 1) * (spD[r] - spD[l]) - (spDD[r] - spDD[l] - (long long)(spD[r] - spD[l]) * l); // for (int d = d2; d > d2 - maxx && d >= d1; d--) // ans += diag[d] * (d2 - d + 1); return ans; } int getSumL(int l1, int c1, int l2, int c2) { return spL[l2][c2] - spL[l2][c1 - 1] - spL[l1 - 1][c2] + spL[l1 - 1][c1 - 1]; } int getSumC(int l1, int c1, int l2, int c2) { return spC[l2][c2] - spC[l2][c1 - 1] - spC[l1 - 1][c2] + spC[l1 - 1][c1 - 1]; } long long getSumRectangle(int l1, int c1, int l2, int c2) { long long ans = getImportantSumRectangle(max(l1, 3), max(c1, 3), l2, c2); if (l1 < 3) ans += getSumL(l1, c1, min(l2, 2), c2); if (c1 < 3) ans += getSumC(l1, c1, l2, min(c2, 2)); if (l1 < 3 && c1 < 3) ans -= getSumL(l1, c1, min(l2, 2), min(c2, 2)); return ans; } vector<long long> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R) { n = X.size(); int q = (int)T.size(); vector<long long> ans(q); for (int c = 1; c <= n; c++) matL[1][c] = X[c - 1]; for (int c = 1; c <= 3; c++) matC[1][c] = X[c - 1]; for (int l = 1; l <= n; l++) matC[l][1] = Y[l - 1]; for (int l = 1; l <= 3; l++) matL[l][1] = Y[l - 1]; for (int d = 0; d <= 2 * n + 1; d++) diag[d] = -1; for (int l = 2; l <= 3; l++) { for (int c = 2; c <= n; c++) matL[l][c] = !(matL[l][c - 1] | matL[l - 1][c]); } for (int c = 2; c <= 3; c++) { for (int l = 2; l <= n; l++) matC[l][c] = !(matC[l][c - 1] | matC[l - 1][c]); } for (int l = 1; l <= 3; l++) { for (int c = 1; c <= n; c++) spL[l][c] = spL[l - 1][c] + spL[l][c - 1] - spL[l - 1][c - 1] + matL[l][c]; } for (int l = 1; l <= n; l++) { for (int c = 1; c <= 3; c++) spC[l][c] = spC[l - 1][c] + spC[l][c - 1] - spC[l - 1][c - 1] + matC[l][c]; } for (int c = 3; c <= n; c++) diag[3 - c + n] = matL[3][c]; for (int l = 3; l <= n; l++) diag[l - 3 + n] = matC[l][3]; for (int d = 1; d <= 2 * n + 1; d++) { spD[d] = spD[d - 1] + diag[d]; spDD[d] = spDD[d - 1] + d * diag[d]; } for (int i = 0; i < q; i++) { int l1 = T[i] + 1, l2 = B[i] + 1, c1 = L[i] + 1, c2 = R[i] + 1; ans[i] = getSumRectangle(l1, c1, l2, c2); } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...