Submission #1109275

#TimeUsernameProblemLanguageResultExecution timeMemory
1109275KerimMosaic (IOI24_mosaic)C++17
100 / 100
892 ms109640 KiB
#include "bits/stdc++.h" #define ll long long #define pb push_back #define pii pair<int, int> using namespace std; const int N = 4e5+5; int cnt[N], arcalyk[4][N], tarhun[N][4]; ll pre[N], suf[N], cep[N], sag[N]; int wow(int a, int b){ return (!(a|b)?1:0); } vector<ll> mosaic(vector<int> X, vector<int> Y, vector<int> T, vector<int> B, vector<int> L, vector<int> R){ int n = (int)X.size(); for (int i = 0; i < n+n; i++) cnt[i] = 0; map<pii, int> mp; for(int i = 1; i <= n; ++i) mp[{1, i}] = X[i-1], mp[{i, 1}] = Y[i-1]; for(int i = 2; i <= n; ++i) for(int j = 2; j <= 3; ++j) mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]); for(int i = 2; i <= 3; ++i) for(int j = 2; j <= n; ++j) mp[{i, j}] = wow(mp[{i-1, j}], mp[{i, j-1}]); int i = 3; for(int j = 3; j <= n; ++j) cnt[i-j+n] = mp[{i, j}]; int j = 3; for(int i = 3; i <= n; ++i) cnt[i-j+n] = mp[{i, j}]; for (int i = 1; i <= 3; i++) for (int j = 1; j <= n; j++) arcalyk[i][j] = mp[{i,j}] + arcalyk[i][j-1]; for (int j = 1; j <= 3; j++) for (int i = 1; i <= n; i++) tarhun[i][j] = mp[{i,j}] + tarhun[i-1][j]; suf[n+n] = cep[n+n] = 0; sag[0] = pre[0] = cnt[0]; for (int i = 1; i < n+n; i++){ pre[i] = pre[i-1] + cnt[i]; sag[i] = sag[i-1] + pre[i-1] + cnt[i]; } for (int i = n+n-1; i >= 0; i--){ suf[i] = suf[i+1] + cnt[i]; cep[i] = cep[i+1] + suf[i+1] + cnt[i]; } vector<ll> ans; for(int i = 0; i < (int)L.size(); ++i){ int x = T[i]+1, y = L[i]+1, yy = R[i]+1, xx = B[i]+1; ll res = 0; while (x <= 3 and x <= xx) res += arcalyk[x][yy]-arcalyk[x][y-1], x += 1; if (x <= xx){ while (y <= 3 and y <= yy) res += tarhun[xx][y]-tarhun[x-1][y], y += 1; } if (x <= xx and y <= yy){ int a = x-y+n, b = x-yy+n, k = xx-x+1; swap(a, b); int len = b-a+1; b += k-1; k = min(k, len); res += cep[a] - (cep[a+k]+k*suf[a+k]); res += sag[b] - (sag[b-k]+k*pre[b-k]); a += k; b -= k; if (a > b) res -= cnt[++b] * 1LL * k; res += (pre[b]-pre[a-1])*1LL*k; } ans.pb(res); } 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...