Submission #1132430

#TimeUsernameProblemLanguageResultExecution timeMemory
1132430alterioMosaic (IOI24_mosaic)C++20
0 / 100
128 ms43608 KiB
#include <bits/stdc++.h> #include "mosaic.h" using namespace std; #define ll long long #define all(x) (x).begin(), (x).end() const int mxn = 2e5 + 100; ll X[3][mxn], Y[mxn][3], prfX[3][mxn], prfY[mxn][3], prf[2 * mxn]; // x - vertical, y - horizontal map<pair<int, int>, int> comp; ll f(int x, int y) { return comp[{x, y}]; } ll get(int x, int y) { if (y < 0) return 0; if (x <= 2) return prfX[x][y]; if (y <= 2) return prfY[x][y]; if (x < y) return prf[f(2, y - (x - 2))]; return prf[f(x - (y - 2), 2)]; } 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(); int q = T.size(); vector<ll> C(q, 0); for (int i = 0; i < n; i++) { X[0][i] = _X[i], Y[i][0] = _Y[i]; prfX[0][i] = (i > 0 ? prfX[0][i - 1] : 0) + X[0][i]; prfY[i][0] = (i > 0 ? prfY[i - 1][0] : 0) + Y[i][0]; } for (int i = 1; i < 3; i++) { X[i][0] = Y[i][0]; for (int j = 1; j < n; j++) { X[i][j] = (!X[i][j - 1] && !X[i - 1][j]); prfX[i][j] = prfX[i][j - 1] + X[i][j]; } } for (int i = 1; i < 3; i++) { Y[0][i] = X[0][i]; for (int j = 1; j < n; j++) { Y[j][i] = (!Y[j][i - 1] && !Y[j - 1][i]); prfY[j][i] = prfX[j - 1][i] + Y[j][i]; } } int cnt = 0; for (int i = n - 1; i <= 2; i--) { prf[cnt] = (cnt > 0 ? prf[cnt - 1] : 0) + Y[i][2]; comp[{i, 2}] = cnt++; } for (int i = 3; i < n; i++) { prf[cnt] = prf[cnt - 1] + X[2][i]; comp[{2, i}] = cnt++; } for (int i = 0; i < q; i++) { C[i] = get(T[i], R[i]) - get(T[i], L[i] - 1); } return C; }
#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...