Submission #563029

#	Time	Username	Problem	Language	Result	Execution time	Memory
563029		Seb	Wall (IOI14_wall)	C++17	100 / 100	916 ms	99296 KiB

wall

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

using namespace std;

typedef int ll;

ll N;

struct Node{
    ll top, bot;
    Node() : top(-1LL), bot(-1LL) {}
};

void push(Node st[], ll nodo, ll ini, ll fin) {
    if (ini!=fin) {
        if (st[nodo].top!=-1) {
            if (st[nodo*2].top!=-1) st[nodo*2].top = min(st[nodo*2].top,st[nodo].top);
            else st[nodo*2].top = st[nodo].top;
            if (st[nodo*2+1].top!=-1) st[nodo*2+1].top = min(st[nodo*2+1].top,st[nodo].top);
            else st[nodo*2+1].top = st[nodo].top;
            if (st[nodo*2].bot>st[nodo*2].top) st[nodo*2].bot = st[nodo*2].top;
            if (st[nodo*2+1].bot>st[nodo*2+1].top) st[nodo*2+1].bot = st[nodo*2+1].top;
            st[nodo].top = -1;
        }
        if (st[nodo].bot!=-1) {
            if (st[nodo*2].bot!=-1) st[nodo*2].bot = max(st[nodo*2].bot,st[nodo].bot);
            else st[nodo*2].bot = st[nodo].bot;
            if (st[nodo*2+1].bot!=-1) st[nodo*2+1].bot = max(st[nodo*2+1].bot,st[nodo].bot);
            else st[nodo*2+1].bot = st[nodo].bot;
            if (st[nodo*2].top!=-1 && st[nodo*2].bot>st[nodo*2].top) st[nodo*2].top = st[nodo*2].bot;
            if (st[nodo*2+1].top!=-1 && st[nodo*2+1].bot>st[nodo*2+1].top) st[nodo*2+1].top = st[nodo*2+1].bot;
            st[nodo].bot = -1;
        }
    }
    return;
}

void merger(Node st[], Node aux, ll nodo) {
    if (aux.top!=-1) {
        if (st[nodo].top!=-1) st[nodo].top = min(st[nodo].top,aux.top);
        else st[nodo].top = aux.top;
        if (st[nodo].bot>st[nodo].top) st[nodo].bot = st[nodo].top;
    }
    if (aux.bot!=-1) {
        if (st[nodo].bot!=-1) st[nodo].bot = max(st[nodo].bot,aux.bot);
        else st[nodo].bot = aux.bot;
        if (st[nodo].top!=-1 && st[nodo].bot>st[nodo].top) st[nodo].top = st[nodo].bot;
    }
    return;
}

void update(Node st[], ll caso, ll l, ll r, ll delta, ll nodo = 1, ll ini = 0, ll fin = N-1) {
    push(st,nodo,ini,fin);
    if (ini>r || fin<l) return;
    if (l<=ini && fin<=r) {
        Node aux;
        if (caso==1) aux.bot = delta;
        else aux.top = delta;
        merger(st,aux,nodo);
        push(st,nodo,ini,fin);
        return;
    }
    update(st,caso,l,r,delta,nodo*2,ini,(ini+fin)/2);
    update(st,caso,l,r,delta,nodo*2+1,(ini+fin)/2+1,fin);
    return;
}

void ans(Node st[], ll pos[], ll nodo = 1, ll ini = 0, ll fin = N-1) {
    push(st,nodo,ini,fin);
    if (ini==fin){
        pos[ini] = max(st[nodo].bot,0);
        return;
    }
    ans(st,pos,nodo*2,ini,(ini+fin)/2);
    ans(st,pos,nodo*2+1,(ini+fin)/2+1,fin);
    return;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
N = n;
ll i,j;
Node st[4*n];
for (i=0;i<k;i++) update(st,op[i],left[i],right[i],height[i]);
ans(st,finalHeight);
return;
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:82:6: warning: unused variable 'j' [-Wunused-variable]
   82 | ll i,j;
      |      ^

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