Submission #1205197

#TimeUsernameProblemLanguageResultExecution timeMemory
1205197HappyCapybara모자이크 (IOI24_mosaic)C++20
100 / 100
109 ms38768 KiB
#include "mosaic.h" #include<bits/stdc++.h> using namespace std; #define ll long long 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(), Q = T.size(); if (N < 4){ vector<vector<int>> bruh(N, vector<int>(N)); bruh[0] = X; for (int i=1; i<N; i++) bruh[i][0] = Y[i]; for (int i=1; i<N; i++){ for (int j=1; j<N; j++) bruh[i][j] = 1-(bruh[i-1][j] | bruh[i][j-1]); } vector<ll> res(Q, 0); for (int k=0; k<Q; k++){ for (int i=T[k]; i<=B[k]; i++){ for (int j=L[k]; j<=R[k]; j++) res[k] += bruh[i][j]; } } return res; } vector<vector<int>> h(3, vector<int>(N)), v(3, vector<int>(N)); h[0] = X; v[0] = Y; for (int i=1; i<3; i++){ h[i][0] = Y[i]; v[i][0] = X[i]; } for (int i=1; i<3; i++){ for (int j=1; j<N; j++){ h[i][j] = 1-(h[i-1][j] | h[i][j-1]); v[i][j] = 1-(v[i-1][j] | v[i][j-1]); } } vector<ll> z; for (int i=N-1; i>=2; i--) z.push_back(v[2][i]); for (int i=3; i<N; i++) z.push_back(h[2][i]); vector<vector<ll>> psh(3, vector<ll>(N+1, 0)), psv(3, vector<ll>(N+1, 0)); for (int i=0; i<3; i++){ for (int j=0; j<N; j++){ psh[i][j+1] = psh[i][j]+h[i][j]; psv[i][j+1] = psv[i][j]+v[i][j]; } } int s = 2*N-5; vector<ll> psz(s+1, 0), zx(s+1), xz(s+1); for (int i=0; i<s; i++){ psz[i+1] = psz[i]+z[i]; zx[i+1] = zx[i]+z[i]*(ll)(i+1); xz[i+1] = xz[i]+z[i]*(ll)(s-i); } vector<ll> res(Q, 0); for (int i=0; i<Q; i++){ for (int j=T[i]; j<=min(B[i], 2); j++) res[i] += psh[j][R[i]+1]-psh[j][L[i]]; if (B[i] >= 3){ for (int j=L[i]; j<=min(R[i], 2); j++) res[i] += psv[j][B[i]+1]-psv[j][max(T[i], 3)]; } if (B[i] < 3 || R[i] < 3) continue; int a = max(3, L[i])-B[i]+(N-3), b = max(3, L[i])-max(3, T[i])+(N-3), c = R[i]-B[i]+(N-3), d = R[i]-max(3, T[i])+(N-3); if (b > c) swap(b, c); //cout << a << " " << b << " " << c << " " << d << endl; res[i] += zx[b]-zx[a]-(psz[b]-psz[a])*(ll)a + xz[d+1]-xz[c+1]-(psz[d+1]-psz[c+1])*(ll)(s-1-d) + (psz[c+1]-psz[b])*(ll)(b-a+1); } return res; }
#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...