Submission #1269878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269878		krzyska	Wall (IOI14_wall)	C++20	100 / 100	392 ms	59180 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int base = (1 << 21);
int minim[base*2];
int maxim[base*2];

int x, a, b;
bool cz;

void zrzuta(int v, int s){
    if(minim[v] > minim[s]){
        minim[s] = minim[v];
        if(maxim[v] < maxim[s]){
            maxim[s] = maxim[v];
        }
        else{
            maxim[s] = max(maxim[s], minim[s]);
        }
    }
    else{
        if(maxim[v] < maxim[s]){
            maxim[s] = maxim[v];
            minim[s] = min(minim[s], maxim[s]);
        }
    }
}

void zmiana(int v, int l, int p){
    if(a <= l && p <= b){
        if(cz){
            minim[v] = max(minim[v], x);
            maxim[v] = max(maxim[v], x);
        }
        else{
            maxim[v] = min(maxim[v], x);
            minim[v] = min(minim[v], x);
        }
        return;
    }
    if(a > p || b < l){
        return;
    }

    zrzuta(v, v*2);
    zrzuta(v, v*2 + 1);
    minim[v] = -100005;
    maxim[v] = 100005;

    zmiana(v*2, l, (l + p)/2);
    zmiana(v*2 + 1, (l + p)/2 + 1, p);
}

void buildWall(int n, int k, int q[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 1; i < base*2; i++){
        minim[i] = -100005;
        maxim[i] = 100005;
    }

    for(int i = 0; i < k; i++){
        a = left[i];
        b = right[i];
        x = height[i];
        if(q[i] == 1){ // dodanie
            cz = 1;
        }
        else{
            cz = 0;
        }
        zmiana(1, 0, base - 1);
    }

    for(int i = 1; i < base; i++){
        zrzuta(i, i*2);
        zrzuta(i, i*2 + 1);
    }
    for(int i = 0; i < n; i++){
        finalHeight[i] = min(max(0, minim[i + base]), maxim[i + base]);
    }
}

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