Submission #1240859

#TimeUsernameProblemLanguageResultExecution timeMemory
1240859madamadam3Mosaic (IOI24_mosaic)C++20
70 / 100
1098 ms302648 KiB
#include "mosaic.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; using vi =vector<int>; using vl = vector<ll>; using vvi = vector<vi>; using vvl = vector<vl>; using pi = pair<int, int>; using vpi = vector<pi>; #ifdef LOCAL #define dout std::cout #else #define dout if (0) std::cout #endif #define pb push_back #define lb lower_bound #define ub upper_bound #define all(x) (x).begin(), (x).end() #define en(x) (x).end() #define bg(x) (x).begin() #define rev(x) reverse(all(x)) #define sz(x) int((x).size()) #define FOR(i, a, b) for (int i = a; i < b; i++) #define each(a, x) for (auto &a : x) #define trace(x) for (auto &el : x) dout << el << " " vl mosaic(vi X, vi Y, vi T, vi B, vi L, vi R) { int Q = sz(T), n = sz(X); if (n <= 5000) { vl C(Q, 0); vvi grid(n, vi(n, 0)); FOR(i, 0, n) { grid[0][i] = X[i]; grid[i][0] = Y[i]; } FOR(i, 1, n) { FOR(j, 1, n) { if (grid[i-1][j] == 0 && grid[i][j-1] == 0) grid[i][j] = 1; else grid[i][j] = 0; } } vvl pref(n+1, vl(n+1, 0)); FOR(i, 0, n) { FOR(j, 0, n) { pref[i+1][j+1] = grid[i][j] + pref[i+1][j]; } FOR(j, 0, n) { pref[i+1][j+1] += pref[i][j+1]; } } // vl prefx(n+1, 0); FOR(i, 0, n) prefx[i+1] = prefx[i] + X[i]; FOR(qn, 0, Q) { int x1 = T[qn], x2 = B[qn], y1 = L[qn], y2 = R[qn]; // C[qn] = prefx[y2+1] - prefx[y1]; C[qn] += pref[x2+1][y2+1]; C[qn] += pref[x1][y1]; C[qn] -= pref[x1][y2+1]; C[qn] -= pref[x2+1][y1]; } return C; } vl C(Q, 0); vvi grid(n, vi(3, 0)); grid[0].resize(n); grid[1].resize(n); grid[2].resize(n); FOR(i, 0, n) { grid[0][i] = X[i]; grid[i][0] = Y[i]; } map<pi, int> coord; map<int, pi> revcoord; int cc = 0; for (int i = n - 1; i >= 3; i--) { coord[{i, 2}] = cc++; revcoord[cc-1] = {i, 2}; } for (int i = 2; i < n; i++) { coord[{2, i}] = cc++; revcoord[cc-1] = {2, i}; } FOR(i, 1, n) { int top = i <= 2 ? n : 3; FOR(j, 1, top) { if (grid[i-1][j] == 0 && grid[i][j-1] == 0) grid[i][j] = 1; else grid[i][j] = 0; } } vl pref(cc+1, 0); FOR(i, 0, cc) pref[i+1] = pref[i] + grid[revcoord[i].first][revcoord[i].second]; vvl prefix(n+1, vl(4, 0)); prefix[0].resize(n+1); prefix[1].resize(n+1); prefix[2].resize(n+1); prefix[3].resize(n+1); FOR(i, 0, n) { int top = i < 3 ? n : 3; FOR(j, 0, top) { prefix[i+1][j+1] = grid[i][j] + prefix[i+1][j]; } } FOR(qn, 0, Q) { int X1 = T[qn], X2 = B[qn], Y1 = L[qn], Y2 = R[qn]; FOR(x1, X1, X2 + 1) { int x2 = x1, y1 = Y1, y2 = Y2; if (x1 <= min(2, n -1)) { C[qn] += prefix[x1+1][y2+1] - prefix[x1+1][y1]; } else { if (y1 <= min(2, n-1)) { C[qn] += prefix[x1+1][min(y2, min(2, n -1)) + 1] - prefix[x1+1][y1]; y1 = min(2, n - 1) + 1; } if (y1 > y2) continue; int lx = x1 - min(x1 - 2, y1 - 2), ly = y1 - min(x1 - 2, y1 - 2); int rx = x1 - min(x1 - 2, y2 - 2), ry = y2 - min(x1 - 2, y2 - 2); int lc = coord[{lx, ly}], rc = coord[{rx, ry}]; C[qn] += pref[rc+1] - pref[lc]; } } } 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...