Submission #1062741

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062741		damjandavkov	Wall (IOI14_wall)	C++17	100 / 100	932 ms	91988 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> mx, mn, wl, wr;
int p, dp, r = 2147483647;
void ac(int i, int x, int n)
{
    if (x > mn[i])
        mx[i] = mn[i] = x;
    else if (n < mx[i])
        mx[i] = mn[i] = n;
    else
    {
        mx[i] = max(mx[i], x);
        mn[i] = min(mn[i], n);
    }
}
void push(int i)
{
    if (i >= p)
        return;
    ac(i << 1, mx[i], mn[i]);
    ac((i << 1) ^ 1, mx[i], mn[i]);
    mx[i] = 0;
    mn[i] = r;
}
void upd(int l, int r, int i, int x, int n)
{
    push(i);
    if (wl[i] >= r || wr[i] <= l)
        return;
    if (wl[i] >= l && wr[i] <= r)
    {
        ac(i, x, n);
        return;
    }
    upd(l, r, i << 1, x, n);
    upd(l, r, (i << 1) ^ 1, x, n);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    p = n;
    while (p != (p & -p))
        p++;
    dp = (p << 1);
    int i;
    pair<int, int> t;
    mx.resize(dp);
    mn.resize(dp);
    wl.resize(dp);
    wr.resize(dp);
    for (i = p; i < dp; i++)
    {
        mx[i] = mn[i] = 0;
        wl[i] = i;
        wr[i] = i + 1;
    }
    for (i = p - 1; i > 0; i--)
    {
        mx[i] = mn[i] = 0;
        wl[i] = wl[i << 1];
        wr[i] = wr[(i << 1) ^ 1];
    }
    for (i = 0; i < k; i++)
    {
        if (op[i] == 1)
            upd(left[i] + p, right[i] + p + 1, 1, height[i], r);
        else
            upd(left[i] + p, right[i] + p + 1, 1, 0, height[i]);
    }
    for (i = 1; i < p; i++)
        push(i);
    for (i = 0; i < n; i++)
        finalHeight[i] = mx[i + p];
    return;
}

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