Submission #1254766

#TimeUsernameProblemLanguageResultExecution timeMemory
1254766Rainmaker2627Mosaic (IOI24_mosaic)C++20
15 / 100
86 ms25416 KiB
#include "mosaic.h" #include <vector> std::vector<long long> preX, preY, preL, sufR, preD; long long query(int N, int T, int B, int L, int R) { long long ans=0; if (T==0) { T=1; ans+=preX[R+1]-preX[L]; if (B==0) return ans; } if (L==0) { L=1; ans+=preY[B+1]-preY[T]; if (R==0) return ans; } if (R-B<L-T) { ans+=(preL[R-B+N-1]-preL[L-B+N-2])-(preD[R-B+N-1]-preD[L-B+N-2])*(L-B+N-2); ans+=(sufR[L-T+N-2]-sufR[R-T+N-1])-(preD[R-T+N-1]-preD[L-T+N-2])*(N-2+T-R); ans+=(R-L+1)*(preD[L-T+N-2]-preD[R-B+N-1]); } else if (R-B>L-T) { ans+=(preL[L-T+N-1]-preL[L-B+N-2])-(preD[L-T+N-1]-preD[L-B+N-2])*(L-B+N-2); ans+=(sufR[R-B+N-2]-sufR[R-T+N-1])-(preD[R-T+N-1]-preD[R-B+N-2])*(N-2+T-R); ans+=(B-T+1)*(preD[R-B+N-2]-preD[L-T+N-1]); } else { ans+=(preL[L-T+N-2]-preL[L-B+N-2])-(preD[L-T+N-2]-preD[L-B+N-2])*(L-B+N-2); ans+=(sufR[R-B+N-2]-sufR[R-T+N-1])-(preD[R-T+N-1]-preD[R-B+N-2])*(N-2+T-R); } return ans; } 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(); std::vector<long long> C(Q, 0); std::vector<int> diag(2*N-3); diag[N-2]=1-(X[1]|Y[1]); for (int i = N-1; i < 2*N-3; i++) diag[i]=1-(diag[i-1]|X[i-N+3]); for (int i = N-3; i >= 0; i--) diag[i]=1-(diag[i+1]|Y[N-1-i]); preX.assign(N+1, 0); preY.assign(N+1, 0); for (int i = 1; i <= N; i++) { preX[i]=preX[i-1]+X[i-1]; preY[i]=preY[i-1]+Y[i-1]; } preL.assign(2*N-2, 0); sufR.assign(2*N-2, 0); preD.assign(2*N-2, 0); for (int i = 1; i <= 2*N-3; i++) { preL[i]=preL[i-1]+i*diag[i-1]; sufR[2*N-3-i]=sufR[2*N-2-i]+i*diag[2*N-3-i]; preD[i]=preD[i-1]+diag[i-1]; } for (int i = 0; i < Q; i++) { C[i]=query(N, T[i], B[i], L[i], R[i]); } 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...