Submission #1207201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207201		Gabriel	Wall (IOI14_wall)	C++17	32 / 100	352 ms	12808 KiB

wall

#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[]){
  if(n <= 10000 and k <= 5000){
    for(int i = 0; i < k; i++){
      for(int j = left[i]; j <= right[i]; j++){
        if(op[i] == 1) finalHeight[j] = max(height[i], finalHeight[j]);
        else finalHeight[j] = min(height[i], finalHeight[j]);
      }
    }
    return;
  }
  _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
*/

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39