Submission #1202354

#TimeUsernameProblemLanguageResultExecution timeMemory
1202354PacybwoahMosaic (IOI24_mosaic)C++20
100 / 100
151 ms70908 KiB
#include "mosaic.h" #include<iostream> #include<algorithm> #include<vector> #include<utility> using namespace std; typedef long long ll; 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> ans(q); if(n < 5){ vector<vector<int>> dp(n, vector<int>(n)); for(int i = 0; i < n; i++){ dp[0][i] = X[i]; dp[i][0] = Y[i]; } for(int i = 1; i < n; i++){ for(int j = 1; j < n; j++){ if(dp[i - 1][j] == 0 && dp[i][j - 1] == 0) dp[i][j] = 1; } } 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++){ ans[i] += dp[j][k]; } } } return ans; } vector<vector<ll>> dpx(6, vector<ll>(n + 1)), dpy(n + 1, vector<ll>(6)), prex(6, vector<ll>(n + 1)), prey(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 <= 5; i++){ for(int j = 2; j <= n; j++){ if(dpx[i - 1][j] == 0 && dpx[i][j - 1] == 0) dpx[i][j] = 1; if(dpy[j - 1][i] == 0 && dpy[j][i - 1] == 0) dpy[j][i] = 1; } } for(int i = 1; i <= 5; i++){ for(int j = 1; j <= n; j++){ prex[i][j] = prex[i - 1][j] + prex[i][j - 1] - prex[i - 1][j - 1] + dpx[i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= 5; j++){ prey[i][j] = prey[i - 1][j] + prey[i][j - 1] - prey[i - 1][j - 1] + dpy[i][j]; } } 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 = 5; i <= n; i++){ px1[i] = px1[i - 1] + dpx[5][i]; py1[i] = py1[i - 1] + dpy[i][5]; } for(int i = 5; i <= n; i++){ px2[i] = px2[i - 1] + px1[i]; py2[i] = py2[i - 1] + py1[i]; } auto get = [&](int x, int y){ if(x <= 5) return prex[x][y]; if(y <= 5) return prey[x][y]; ll res = prex[4][y] + prey[x][4] - prex[4][4]; int w = min(x - 4, y - 4); res -= dpx[5][5] * w; res += px2[y] - px2[y - w]; res += py2[x] - py2[x - w]; return res; }; for(int i = 0; i < q; i++){ ans[i] = get(B[i], R[i]) - get(B[i], L[i] - 1) - get(T[i] - 1, R[i]) + get(T[i] - 1, L[i] - 1); } 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...