Submission #562598

#	Time	Username	Problem	Language	Result	Execution time	Memory
562598		Seb	Wall (IOI14_wall)	C++17	0 / 100	143 ms	13936 KiB

wall

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

using namespace std;

typedef int ll;

ll N;

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

void push(Node st[], ll nodo, ll ini, ll fin) {
    if (ini!=fin) {
        if (st[nodo].top!=0) {
            st[nodo*2].top = min(st[nodo*2].top,st[nodo].top);
            if (st[nodo*2].top < st[nodo*2].bot) st[nodo*2].bot = st[nodo*2].top;
            st[nodo*2+1].top = min(st[nodo*2+1].top,st[nodo].top);
            if (st[nodo*2+1].top < st[nodo*2+1].bot) st[nodo*2+1].bot = st[nodo*2+1].top;
            st[nodo].top = 0;
        }
        if (st[nodo].bot!=0) {
            st[nodo*2].bot = max(st[nodo*2].bot,st[nodo].bot);
            if (st[nodo*2].top < st[nodo*2].bot) st[nodo*2].top = st[nodo*2].bot;
            st[nodo*2+1].bot = max(st[nodo*2+1].bot,st[nodo].bot);
            if (st[nodo*2+1].top < st[nodo*2+1].bot) st[nodo*2+1].top = st[nodo*2+1].bot;
            st[nodo].bot = 0;
        }
    }
    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) {
        if (caso==1) st[nodo].bot = delta;
        else st[nodo].top = delta;
        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] = st[nodo].bot;
        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;
Node st[4*n];
for (i=0;i<k;i++) {
    update(st,op[i],left[i],right[i],height[i]);
}
ans(st,finalHeight);
return;
}

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