Submission #1203456

#TimeUsernameProblemLanguageResultExecution timeMemory
1203456tamyteMosaic (IOI24_mosaic)C++20
100 / 100
152 ms70908 KiB
#include <bits/stdc++.h> #include "mosaic.h" using namespace std; using ll = long long; 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 N = (int)X.size(); int Q = (int)T.size(); vector<ll> C(Q); if (N <= 5) { vector<vector<int>> dp(N, vector<int>(N)); for (int i = 0; i < N; ++i) { dp[i][0] = Y[i]; dp[0][i] = X[i]; } for (int i = 1; i < N; ++i) { for (int j = 1; j < N; ++j) { dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] == 0); } } for (int i = 0; i < Q; ++i) { for (int j = T[i]; j <= B[i]; ++j) { for (int k = L[i]; k <= R[i]; ++k) { C[i] += dp[j][k]; } } } return C; } vector<vector<ll>> dpx(6, vector<ll>(N + 1)), dpy(N + 1, vector<ll>(6)), psx(6, vector<ll>(N + 1)), psy(N + 1, vector<ll>(6)); for (int i = 0; i < N; ++i) { dpx[1][i + 1] = X[i]; dpy[i + 1][1] = Y[i]; if (i < 5) { dpx[i + 1][1] = Y[i]; dpy[1][i + 1] = X[i]; } } for (int i = 2; i <= 3; ++i) { for (int j = 2; j <= N; ++j) { dpx[i][j] = (dpx[i - 1][j] + dpx[i][j - 1] == 0); dpy[j][i] = (dpy[j - 1][i] + dpy[j][i - 1] == 0); } } for (int i = 1; i <= 3; ++i) { for (int j = 1; j <= N; ++j) { psx[i][j] = psx[i - 1][j] + psx[i][j - 1] - psx[i - 1][j - 1] + dpx[i][j]; psy[j][i] = psy[j - 1][i] + psy[j][i - 1] - psy[j - 1][i - 1] + dpy[j][i]; } } for (int i = 0; i < Q; ++i) {T[i]++; B[i]++; L[i]++; R[i]++;} vector<ll> px1(N + 1), py1(N + 1), px2(N + 1), py2(N + 1); for (int i = 3; i <= N; ++i) { px1[i] = px1[i - 1] + dpx[3][i]; py1[i] = py1[i - 1] + dpy[i][3]; px2[i] = px2[i - 1] + px1[i]; py2[i] = py2[i - 1] + py1[i]; } auto sum = [&](int x, int y) -> ll { if (x <= 3) return psx[x][y]; if (y <= 3) return psy[x][y]; ll res = psx[2][y] + psy[x][2] - psx[2][2]; int excl = min(x - 2, y - 2); res -= 1LL * excl * dpx[3][3]; res += px2[y] - px2[y - excl]; res += py2[x] - py2[x - excl]; return res; }; for (int i = 0; i < Q; ++i) { C[i] = sum(B[i], R[i]) - sum(T[i] - 1, R[i]) - sum(B[i], L[i] - 1) + sum(T[i] - 1, L[i] - 1); } return C;; } /* int main() { int N; assert(1 == scanf("%d", &N)); std::vector<int> X(N), Y(N); for (int i = 0; i < N; i++) assert(1 == scanf("%d", &X[i])); for (int i = 0; i < N; i++) assert(1 == scanf("%d", &Y[i])); int Q; assert(1 == scanf("%d", &Q)); std::vector<int> T(Q), B(Q), L(Q), R(Q); for (int k = 0; k < Q; k++) assert(4 == scanf("%d%d%d%d", &T[k], &B[k], &L[k], &R[k])); fclose(stdin); std::vector<long long> C = mosaic(X, Y, T, B, L, R); int S = (int)C.size(); for (int k = 0; k < S; k++) printf("%lld\n", C[k]); fclose(stdout); return 0; }*/
#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...