oj.uz

Submission #421978

# Submission time Handle Problem Language Result Execution time Memory
421978 2021-06-09T14:23:46 Z Ozy Wall (IOI14_wall) C++17
100 / 100
 1166 ms 117992 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl

#define MAX 4500002
#define INF 1000000000

#define sube 1
#define baja 2


lli h[MAX], arriba[MAX], abajo[MAX];
lli ult,offset;

void push(lli nodo, lli s, lli e){
    lli hijo;

    if (s == e){
        h[nodo] = max(h[nodo], abajo[nodo]);
        h[nodo] = min(h[nodo], arriba[nodo]);
        abajo[nodo] = 0;
        arriba[nodo] = INF;
        return;
    }

    hijo = nodo * 2;
    arriba[hijo] = min(arriba[hijo], arriba[nodo]);
    abajo[hijo] = min(abajo[hijo], arriba[nodo]);
    arriba[hijo] = max(arriba[hijo], abajo[nodo]);
    abajo[hijo] = max(abajo[hijo], abajo[nodo]);

    hijo++;
    arriba[hijo] = min(arriba[hijo], arriba[nodo]);
    abajo[hijo] = min(abajo[hijo], arriba[nodo]);
    arriba[hijo] = max(arriba[hijo], abajo[nodo]);
    abajo[hijo] = max(abajo[hijo], abajo[nodo]);

    abajo[nodo] = 0;
    arriba[nodo] = INF;
}

void update(lli nodo, lli s, lli e, lli l, lli r, lli altura, lli tipo){
    push(nodo, s, e); // EMPUJA A LOS HIJOS

    if (s > r || e < l) return; // SI EL RANGO A ACTUALIZAR ESTA FUERA DE ESTE NO HAGAS NADA
    if (s == e){ // SI EL RANGO A ACTUALIZAR ES DE 1 ENTONCES ES HOJA, MODIFICA SU ALTURA
        if (tipo == sube) h[nodo] = max(h[nodo], altura);
        else if (tipo == baja) h[nodo] = min(h[nodo], altura);
    }
    if (s >= l && e <= r){ // SI EL RANGO ESTA COMPLETAMENTE CONTENIDO MODIFICA EL LIMITE
        if (tipo == sube) abajo[nodo] = max(abajo[nodo], altura);
        else if (tipo == baja) arriba[nodo] = min(arriba[nodo], altura);
        return;
    }

    lli mitad = (s + e) / 2;
    update(nodo * 2, s, mitad, l, r, altura, tipo);
    update(nodo * 2 + 1, mitad + 1, e, l, r, altura, tipo);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    offset = 1;
    while (offset <= n) offset *= 2;

    repa(i, offset - 1, 1){
        arriba[i] = INF;
        abajo[i] = 0;
    }

    rep(i, 0, k - 1) update(1, 0, offset - 1, left[i], right[i], height[i], op[i]);

    rep(i, 1, offset - 1) push(i, 0, n - 1);
    rep(i, offset, offset + n - 1) push(i, i, i);

    rep(i, offset, offset + n - 1) finalHeight[i - offset] = h[i];

    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 1084 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 6 ms 1076 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 205 ms 13960 KB Output is correct
3 Correct 273 ms 8600 KB Output is correct
4 Correct 757 ms 23164 KB Output is correct
5 Correct 431 ms 24228 KB Output is correct
6 Correct 422 ms 22688 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 9 ms 1132 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 7 ms 1136 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 197 ms 14048 KB Output is correct
9 Correct 241 ms 8596 KB Output is correct
10 Correct 719 ms 23172 KB Output is correct
11 Correct 453 ms 24236 KB Output is correct
12 Correct 441 ms 22664 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 195 ms 13852 KB Output is correct
15 Correct 36 ms 2656 KB Output is correct
16 Correct 785 ms 23400 KB Output is correct
17 Correct 464 ms 22892 KB Output is correct
18 Correct 481 ms 22880 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 9 ms 1152 KB Output is correct
5 Correct 8 ms 1140 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 203 ms 13832 KB Output is correct
9 Correct 285 ms 8588 KB Output is correct
10 Correct 762 ms 23220 KB Output is correct
11 Correct 458 ms 24204 KB Output is correct
12 Correct 450 ms 22592 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 187 ms 13880 KB Output is correct
15 Correct 38 ms 2656 KB Output is correct
16 Correct 780 ms 23456 KB Output is correct
17 Correct 454 ms 22852 KB Output is correct
18 Correct 475 ms 22800 KB Output is correct
19 Correct 1099 ms 117992 KB Output is correct
20 Correct 1036 ms 115408 KB Output is correct
21 Correct 1126 ms 117924 KB Output is correct
22 Correct 1113 ms 115464 KB Output is correct
23 Correct 1166 ms 115412 KB Output is correct
24 Correct 997 ms 115440 KB Output is correct
25 Correct 1006 ms 115384 KB Output is correct
26 Correct 991 ms 117908 KB Output is correct
27 Correct 1014 ms 117988 KB Output is correct
28 Correct 973 ms 115384 KB Output is correct
29 Correct 1010 ms 115412 KB Output is correct
30 Correct 961 ms 115404 KB Output is correct