Submission #1207192

#TimeUsernameProblemLanguageResultExecution timeMemory
1207192GabrielWall (IOI14_wall)C++17
24 / 100
351 ms12808 KiB
#include "wall.h" #include "bits/stdc++.h" using namespace std; /*struct Nodo{ int A_adir, Remover; };*/ vector<int> _rbol, Propagable, a; bool Cambio = 1; //vector<Nodo> Propagable; //Nodo Nada; /*void Propagar(int p){ if(Propagable[p].A_adir == -22 and Propagable[p].Remover != -22){ _rbol[p] = min(Propagable[p].Remover, _rbol[p]); if(p * 2 < _rbol.size()){ if(Propagable[p * 2].A_adir == -22 and Propagable[p * 2].Remover == -22) Propagable[p * 2].Remover = Propagable[p].Remover; else if(Propagable[p * 2].A_adir == -22) Propagable[p * 2].Remover = min(Propagable[p * 2].Remover, Propagable[p].Remover); else if(Propagable[p * 2].Remover == -22){ if(Propagable[p * 2].A_adir >) } } } else if(Propagable[p].A_adir != -22 and Propagable[p].Remover == -22){ _rbol[p] = max(Propagable[p].Remover, _rbol[p]); } } int Consulta(int i, int d, int p, int I){ Propagar(p); if(i == I and d == I) return _rbol[p]; if(i > I or d < I) return -0; int P = (i + d) / 2; return Consulta(i, P, p * 2, I) + Consulta(P + 1, d, p * 2 + 1, I); } void Actualizar(int i, int d, int p, int I, int D, int v, bool t){ Propagar(p); if(i >= I and d <= D){ if(t == 0) Propagable[p].A_adir = v; else Propagable[p].Remover = v; Propagar(p); return; } if(i > D or d < I) return; int P = (i + d) / 2; Actualizar(i, P, p * 2, I, D, v, t); Actualizar(P + 1, d, p * 2 + 1, I, D, v, t); }*/ void Propagar(int p){ if(Propagable[p] != -22){ //cerr<<p<<" "<<Propagable[p]<<" "<<_rbol[p]<<" "<<(int)Cambio<<"\n"; if(Cambio){ _rbol[p] = max(_rbol[p], Propagable[p]); //cerr<<p<<" -> "<<_rbol[p]<<"\n"; if(p * 2 < _rbol.size()) Propagable[p * 2] = max(Propagable[p * 2], Propagable[p]); if(p * 2 + 1 < _rbol.size()) Propagable[p * 2 + 1] = max(Propagable[p * 2 + 1], Propagable[p]); } else { _rbol[p] = min(_rbol[p], Propagable[p]); //cerr<<p<<" -> "<<_rbol[p]<<"\n"; if(p * 2 < _rbol.size()){ if(Propagable[p * 2] == -22) Propagable[p * 2] = Propagable[p]; else Propagable[p * 2] = min(Propagable[p * 2], Propagable[p]); } if(p * 2 + 1 < _rbol.size()){ if(Propagable[p * 2 + 1] == -22) Propagable[p * 2 + 1] = Propagable[p]; else Propagable[p * 2 + 1] = min(Propagable[p * 2 + 1], Propagable[p]); } } } Propagable[p] = -22; } void Crear(int i, int d, int p){ if(i == d){ _rbol[p] = a[i]; return; } int P = (i + d) / 2; Crear(i, P, p * 2); Crear(P + 1, d, p * 2 + 1); } int Consulta(int i, int d, int p, int I){ Propagar(p); //cerr<<i<<" "<<d<<" "<<p<<" "<<I<<" "<<_rbol[p]<<"\n"; if(i == I and d == I) return _rbol[p]; if(i > I or d < I) return -0; int P = (i + d) / 2; return Consulta(i, P, p * 2, I) + Consulta(P + 1, d, p * 2 + 1, I); } void Actualizar(int i, int d, int p, int I, int D, int v){ Propagar(p); if(i >= I and d <= D){ Propagable[p] = v; Propagar(p); return; } if(i > D or d < I) return; int P = (i + d) / 2; Actualizar(i, P, p * 2, I, D, v); Actualizar(P + 1, d, p * 2 + 1, I, D, v); } void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){ _rbol.assign(n * 4 + 22, 0); a.assign(n, 0); /*Nada.A_adir = -22; Nada.Remover = -22; Propagable.assign(n * 4 + 22, Nada);*/ Propagable.assign(n * 4 + 22, -22); Crear(0, n - 1, 1); for(int i = 0; i < k; i++){ if(op[i] == 2 and Cambio){ for(int j = 0; j < n; j++){ a[j] = Consulta(0, n - 1, 1, j); //cerr<<a[j]<<" "; } //cerr<<"\n"; Cambio = 0; Crear(0, n - 1, 1); Propagable.assign(n * 4 + 22, -22); } Actualizar(0, n - 1, 1, left[i], right[i], height[i]); /*for(int j = 0; j < n; j++) cerr<<Consulta(0, n - 1, 1, j)<<" "; cerr<<"\n";*/ /*for(int j = 0; j < n * 4 + 22; j++) cerr<<Propagable[j]<<" "; cerr<<"\n";*/ } for(int i = 0; i < n; i++){ finalHeight[i] = Consulta(0, n - 1, 1, i); //cerr<<finalHeight[i]<<" "; } //cerr<<"\n"; return; } /* 4 6 1 0 3 5 1 0 1 3 1 2 3 7 2 0 1 8 2 1 3 6 2 0 2 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...