Submission #1108613

#TimeUsernameProblemLanguageResultExecution timeMemory
1108613LudisseyMosaic (IOI24_mosaic)C++17
12 / 100
1196 ms1659564 KiB
#include "mosaic.h" #include <bits/stdc++.h> #define int long long #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() using namespace std; int q,n; vector<vector<int>> lft; vector<vector<int>> top; vector<int> dia; // X cest le top // Y cest la gauche // [le x][le y] int todia(int x, int y){ return (n-x-1)+y; } std::vector<long long> mosaic(std::vector<signed> X, std::vector<signed> Y, std::vector<signed> T, std::vector<signed> B,std::vector<signed> L, std::vector<signed> R) { q = sz(T); n=sz(Y); lft.resize(3,vector<int>(n,0)); top.resize(n,vector<int>(3,0)); dia.resize(n+n+4,0); for (int i = 0; i < n; i++) { lft[0][i]=Y[i]; top[i][0]=X[i]; } if(n>1){ lft[1][0]=X[1]; top[0][1]=Y[1]; if(n>2){ lft[2][0]=X[2]; top[0][2]=Y[2]; } } for (int i = 1; i < n&&n>1; i++) { top[i][1]=(top[i-1][1]==0&&top[i][0]==0); lft[1][i]=(lft[1][i-1]==0&&lft[0][i]==0); } for (int i = 1; i < n&&n>2; i++) { top[i][2]=(top[i-1][2]==0&&top[i][1]==0); lft[2][i]=(lft[2][i-1]==0&&lft[1][i]==0); dia[todia(i,2)]=top[i][2]; dia[todia(2,i)]=lft[2][i]; } vector<vector<int>> fullgrid(n,vector<int>(n,0)); vector<vector<int>> fakegrid(n,vector<int>(n,0)); vector<vector<int>> prefix(n,vector<int>(n,0)); for (int i = 0; i < n; i++){ for (int j = 0; j < min(n,3LL); j++) { fullgrid[i][j]=top[i][j]; fullgrid[j][i]=lft[j][i]; } } for (int i = 0; i < n; i++) { fakegrid[i][0]=X[i]; fakegrid[0][i]=Y[i]; } for (int i = 1; i < n; i++){ for (int j = 1; j < n; j++) { fakegrid[i][j]=(fakegrid[i-1][j]==0&&fakegrid[i][j-1]==0); } } for (int i = 3; i < n; i++){ for (int j = 3; j < n; j++) { fullgrid[i][j]=dia[todia(i,j)]; fullgrid[j][i]=dia[todia(j,i)]; } } for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++) { prefix[i][j]=fullgrid[i][j]; if(i>0) prefix[i][j]+=prefix[i-1][j]; if(j>0) prefix[i][j]+=prefix[i][j-1]; if(i>0&&j>0) prefix[i][j]-=prefix[i-1][j-1]; //cerr << fullgrid[j][i] << " "; } //cerr << "\n"; } //cerr<<"\n"; for (int i = 0; i < n; i++){ for (int j = 0; j < n; j++) { //cerr << fakegrid[j][i] << " "; //if(fakegrid[j][i]!=fullgrid[j][i]) //cerr << "ERROR - " << i << " " << j << "\n"; assert(fakegrid[j][i]==fullgrid[j][i]); } //cerr << "\n"; } std::vector<long long> C(q, 0); for (int i = 0; i < q; i++) { int l=L[i],r=R[i],t=T[i],b=B[i]; int sm=prefix[r][b]; if(l>0) sm-=prefix[l-1][b]; if(t>0) sm-=prefix[r][t-1]; if(l>0&&t>0) sm+=prefix[l-1][t-1]; C[i]=sm; } 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...