Submission #805404

#	Time	Username	Problem	Language	Result	Execution time	Memory
805404		HaroldVemeno	Wall (IOI14_wall)	C++17	100 / 100	511 ms	69516 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int n;
int s;
int lbs[8000000];
int ubs[8000000];

void push(int x) {
    if(x >= s) return;
    for(int c : {2*x, 2*x+1}) {
        lbs[c] = max(lbs[c], lbs[x]);
        lbs[c] = min(lbs[c], ubs[x]);
        ubs[c] = min(ubs[c], ubs[x]);
        ubs[c] = max(ubs[c], lbs[x]);
    }
    ubs[x] = 100000;
    lbs[x] = 0;
}

void walk(int l, int r, int op, int h, int u, int lu, int ru) {
    D(l)
    D(r)
    D(u)
    D(lu)
    D(ru)
    if(r <= lu || ru <= l) return;
    if(l <= lu && ru <= r) {
        if(op == 1) {
            lbs[u] = max(lbs[u], h);
            ubs[u] = max(ubs[u], lbs[u]);
        } else {
            ubs[u] = min(ubs[u], h);
            lbs[u] = min(lbs[u], ubs[u]);
        }
        return;
    }
    push(u);
    int mu = (lu+ru)/2;
    walk(l, r, op, h, 2*u  , lu, mu);
    walk(l, r, op, h, 2*u+1, mu, ru);
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    n = N;
    s = 1;
    while(s < n) s *= 2;
    for(int i = s-1; i > 0; --i) {
        ubs[i] = 100000;
    }
    for(int i = 0; i < k; ++i) {
        walk(left[i], right[i]+1, op[i], height[i], 1, 0, s);
    }
    for(int i = 1; i < s; ++i) {
        push(i);
    }
    for(int i = 0; i < n; ++i) {
        finalHeight[i] = lbs[s+i];
    }

}

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