Submission #679487

#	Time	Username	Problem	Language	Result	Execution time	Memory
679487		kilikuma	Wall (IOI14_wall)	C++14	24 / 100	216 ms	21336 KiB

wall

#include <bits/stdc++.h>
#include <wall.h>
using namespace std;
const int INFINI = 200000;
int arbreBinaireMin[(1 << 18)];
int arbreBinaireMax[(1 << 18)];
void initialise() {
  for (int i = 0; i < (1 << 18); i ++) {
    arbreBinaireMin[i] = INFINI;
    arbreBinaireMax[i] = 0;
  }
}
int corr(int ind) {
  return ind + (1 << 17);
}
int valMin(int ind) {
  int miniCur = INFINI;
  while (ind > 0) {
    miniCur = min(miniCur, arbreBinaireMin[ind]);
    ind /= 2;
  }
  return miniCur;
}
int valMax(int ind) {
  int maxiCur = 0;
  while (ind > 0) {
    maxiCur = max(maxiCur, arbreBinaireMax[ind]);
    ind /= 2;
  }
  return maxiCur;
}
void interMin(int L, int R, int val) {
  if (L > R)
    return;
  if (L == R) {
    arbreBinaireMin[L] = min(arbreBinaireMin[L], val);
  }
  if (L % 2) {
    arbreBinaireMin[L] = min(arbreBinaireMin[L], val);
    L ++;
  }
  if (! (R % 2)) {
    arbreBinaireMin[R] = min(arbreBinaireMin[R], val);
    R --;
  }
  interMin(L / 2, R / 2, val);
}
void interMax(int L, int R, int val) {
  if (L > R)
    return;
  if (L == R) {
    arbreBinaireMax[L] = max(arbreBinaireMax[L], val);
  }
  if (L % 2) {
    arbreBinaireMax[L] = max(arbreBinaireMax[L], val);
    L ++;
  }
  if (! (R % 2)) {
    arbreBinaireMax[R] = max(arbreBinaireMax[R], val);
    R --;
  }
  interMax(L / 2, R / 2, val);
}


void buildWall(int N, int K, int operations[], int gauche[], int droite[], int hauteur[], int hauteurFinale[]) {
  for (int i = 0; i < N; i ++)
    hauteurFinale[i] = 0;
  initialise();
  for (int iOperation = 0; iOperation < K; iOperation ++) {
    if (operations[iOperation] == 1) {
      interMax(corr(gauche[iOperation]), corr(droite[iOperation]), hauteur[iOperation]);
    }
    else {
      interMin(corr(gauche[iOperation]), corr(droite[iOperation]), hauteur[iOperation]);
    }
  }
  for (int i = 0; i < N; i ++)
    hauteurFinale[i] = min(valMax(corr(i)), valMin(corr(i)));
}

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