Submission #426114

#	Time	Username	Problem	Language	Result	Execution time	Memory
426114		JeanBombeur	Wall (IOI14_wall)	C++17	100 / 100	949 ms	62088 KiB

wall

#include <iostream>
#include <cstdio>
#include "wall.h"
using namespace std;

const int INFINI = (1000 * 1000 * 1000);
const int TAILLE_ARBRE = (1 << 21);

pair <int, int> Tree[2 * TAILLE_ARBRE];

void Push(int noeud) {
    if (noeud >= TAILLE_ARBRE)
        return;
    for (int d = 0; d < 2; d ++)
    {
        Tree[2 * noeud + d] = {max(Tree[2 * noeud + d].first, Tree[noeud].first), min(Tree[2 * noeud + d].second, Tree[noeud].second)};
        Tree[2 * noeud + d] = {min(Tree[2 * noeud + d].first, Tree[noeud].second), max(Tree[2 * noeud + d].second, Tree[noeud].first)};
    }
    Tree[noeud] = {0, INFINI};
    return;
}

void AddNew(int noeud, int gauche, int droite, int inf, int sup, pair <int, int> update) {
    if (gauche >= sup || droite <= inf)
        return;
    Push(noeud);
    if (inf <= gauche && droite <= sup)
    {
        if (noeud < TAILLE_ARBRE)
            Tree[noeud] = update;
        else
            Tree[noeud].first = Tree[noeud].second = min(max(Tree[noeud].first, update.first), update.second);
        return;
    }
    int mid = (gauche + droite) / 2;
    AddNew(2 * noeud, gauche, mid, inf, sup, update);
    AddNew(2 * noeud + 1, mid, droite, inf, sup, update);
    return;
}

void buildWall(int nbColonnes, int nbOperations, int TypeOp[], int Left[], int Right[], int Hauteur[], int Ans[]){
    
    for (int i = 0; i < nbOperations; i ++)
    {
        if (TypeOp[i] == 1)
            AddNew(1, 0, TAILLE_ARBRE, Left[i], Right[i] + 1, {Hauteur[i], INFINI});
        else
            AddNew(1, 0, TAILLE_ARBRE, Left[i], Right[i] + 1, {0, Hauteur[i]});
    }
    for (int i = 1; i < TAILLE_ARBRE; i ++)
    {
        Push(i);
    }
    for (int i = 0; i < nbColonnes; i ++)
    {
        Ans[i] = Tree[i + TAILLE_ARBRE].first;
    }
    return;
}

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