Submission #422113

#	Time	Username	Problem	Language	Result	Execution time	Memory
422113		Ozy	Wall (IOI14_wall)	C++17	0 / 100	3063 ms	13928 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debugsl(a) cout << #a << " = " << a << ", "
#define debug(a) cout << #a << " = " << a << endl

#define MAX 4500002
#define INF 1000000000

#define sube 1
#define baja 2

lli offset;
lli st[400002];

void cambia(lli pos, lli val) {
    if (val < 0) st[pos] = min(st[pos], abs(val));
    else st[pos] = max(st[pos], val);
}

void push(lli pos) {

    if (pos >= offset || st[pos] == 0) return;

    if ((pos*2) >= offset) {
        cambia(pos*2,st[pos]);
        cambia((pos*2)+1,st[pos]);
    }
    else {
        push(pos * 2);
        st[pos*2] = st[pos];

        push((pos * 2)+1);
        st[(pos*2)+1] = st[pos];
    }
    st[pos] = 0;
}

void actualiza(lli pos, lli l, lli r, lli ini, lli fin, lli val) {

    push(pos);

    if (ini > r || fin < l) return;
    if (l <= ini && fin <= r) {
        if (ini == fin) cambia(pos,val);
        else st[pos] = val;
    }
    else {
        lli mitad=(ini+fin)/2;
        actualiza(pos*2, l, r, ini, mitad, val);
        actualiza((pos*2)+1, l, r, mitad+1, fin, val);
    }

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){

    offset = 1;
    while (offset < n) offset *= 2;

    rep(i,0,k-1) {
        if (op[i] == 1) actualiza(1,left[i],right[i],0,offset-1,height[i]);
        else actualiza(1,left[i],right[i],0,offset-1,-height[i]);
    }

    rep(i,1,offset-1) push(i);
    rep(i,0,n-1) finalHeight[i] = st[i+offset];

    return;
}

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