Submission #679489

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
679489	2023-01-08T12:11:28 Z	kilikuma	Wall (IOI14_wall)	C++14	32 / 100	215 ms	21416 KB

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;
  if ((N <= 10000) and (K <= 5000)) {
    for (int iOperation = 0; iOperation < K; iOperation ++) {
        if (operations[iOperation] == 1) {
          for (int indice = gauche[iOperation]; indice <= droite[iOperation]; indice ++) {
            if (hauteurFinale[indice] <= hauteur[iOperation])
              hauteurFinale[indice] = hauteur[iOperation];
          }
        }
        else {
          for (int indice = gauche[iOperation]; indice <= droite[iOperation]; indice ++) {
            if (hauteurFinale[indice] >= hauteur[iOperation])
              hauteurFinale[indice] = hauteur[iOperation];
          }
        }
    }
    return; 
  }
  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

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	14 ms	508 KB	Output is correct
5	Correct	14 ms	512 KB	Output is correct
6	Correct	15 ms	444 KB	Output is correct

Subtask #2

24.0 / 24.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	119 ms	10120 KB	Output is correct
3	Correct	82 ms	5748 KB	Output is correct
4	Correct	201 ms	10744 KB	Output is correct
5	Correct	159 ms	11324 KB	Output is correct
6	Correct	142 ms	11260 KB	Output is correct

Subtask #3

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	388 KB	Output is correct
3	Correct	1 ms	316 KB	Output is correct
4	Correct	14 ms	448 KB	Output is correct
5	Correct	14 ms	508 KB	Output is correct
6	Correct	15 ms	496 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	126 ms	15964 KB	Output is correct
9	Correct	95 ms	9384 KB	Output is correct
10	Correct	209 ms	20344 KB	Output is correct
11	Correct	154 ms	21348 KB	Output is correct
12	Correct	148 ms	19752 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Incorrect	125 ms	15908 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #4

0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	14 ms	508 KB	Output is correct
5	Correct	15 ms	468 KB	Output is correct
6	Correct	14 ms	504 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	120 ms	15924 KB	Output is correct
9	Correct	89 ms	9456 KB	Output is correct
10	Correct	215 ms	20300 KB	Output is correct
11	Correct	159 ms	21416 KB	Output is correct
12	Correct	154 ms	19864 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Incorrect	122 ms	15900 KB	Output isn't correct
15	Halted	0 ms	0 KB	-