Submission #1238749

#TimeUsernameProblemLanguageResultExecution timeMemory
1238749porquenomedejainiciarsesionMosaic (IOI24_mosaic)C++20
29 / 100
1006 ms2162688 KiB
#include "mosaic.h" #include <bits/stdc++.h> using namespace std; vector<vector<int>> build_prefix_sum(const vector<vector<int>>& v){ int n=v.size(); vector<vector<int>> p(n+1,vector<int>(n+1)); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ p[i][j]=v[i-1][j-1]+p[i-1][j]+p[i][j-1]-p[i-1][j-1]; } } return p; } int query(const vector<vector<int>>& p,int t,int b,int l,int r){ t++,b++,l++,r++; return p[b][r]-p[t-1][r]-p[b][l-1]+p[t-1][l-1]; } vector<long long> mosaic(vector<int> x,vector<int> y,vector<int> t,vector<int> b,vector<int> l,vector<int> r){ bool ok=true; for(int i=0;i<t.size();i++){ if(t[i]!=0 || b[i]!=0){ ok=false; } } if(ok){ vector<int> Px; Px.push_back(0); for(int i=0;i<x.size();i++){ Px.push_back(Px[i]+x[i]); } vector<long long> ans; for(int i=0;i<t.size();i++){ ans.push_back(Px[r[i]+1]-Px[l[i]]); } return ans; } int n=x.size(); vector<vector<int>> v(n,vector<int>(n)); for(int i=0;i<n;i++)v[0][i]=x[i]; for(int i=0;i<n;i++)v[i][0]=y[i]; for(int i=1;i<n;i++){ for(int j=1;j<n;j++){ v[i][j]=(v[i-1][j]==0 && v[i][j-1]==0); } } vector<vector<int>> p=build_prefix_sum(v); vector<long long> ans; for(int i=0;i<t.size();i++)ans.push_back(query(p,t[i],b[i],l[i],r[i])); 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...