Submission #428729

#	Time	Username	Problem	Language	Result	Execution time	Memory
428729		_ani	Wall (IOI14_wall)	C++17	61 / 100	3079 ms	93520 KiB

wall

#include "wall.h"
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 2'000'002;

int add[4 * maxn], sub[4 * maxn];

void Comp(int v, int h, int t)
{
    if (h == -1) return;
    if (add[v] == -1 && sub[v] == -1)
    {
        if (t == 1) add[v] = h;
        else sub[v] = h;
        return;
    }
    if (t == 1 && add[v] != -1)
    {
        add[v] = max(add[v], h);
        if (sub[v] != -1 && sub[v] < add[v])
            sub[v] = add[v];
        return;
    }
    if (t == 2 && sub[v] != -1)
    {
        sub[v] = min(sub[v], h);
        if (add[v] != -1 && sub[v] < add[v])
            add[v] = sub[v];
        return;
    }
    if (t == 1)
    {
        if (h >= sub[v])
        {
            sub[v] = add[v] = h;
            return;
        }
        add[v] = h;
        return;
    }
    if (h <= add[v])
    {
        sub[v] = add[v] = h;
        return;
    }
    sub[v] = h;
    return;
}
void Push(int v)
{
    Comp(v * 2, add[v], 1);
    Comp(v * 2, sub[v], 2);
    Comp(v * 2 + 1, add[v], 1);
    Comp(v * 2 + 1, sub[v], 2);
    add[v] = sub[v] = -1;
}
void Upd(int v, int vl, int vr, int l, int r, int h, int t)
{
    if (r < l) return;
    if (vl == l && vr == r)
    {
        Comp(v, h, t);
        return;
    }
    int m = (vl + vr) / 2;
    Push(v);
    Upd(v * 2, vl, m, l, min(m, r), h, t);
    Upd(v * 2 + 1, m + 1, vr, max(l, m + 1), r, h, t);
}
pair<int, int> Get(int v, int vl, int vr, int pos)
{
    if (vl == vr)
        return {add[v], sub[v]};
    int m = (vl + vr) / 2;
    Push(v);
    if (pos <= m)
        return Get(v * 2, vl, m, pos);
    else return Get(v * 2 + 1, m + 1, vr, pos);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
     for (int i = 0; i < 4 * maxn; i++)
        sub[i] = add[i] = -1;
    for (int i = 0; i < k; i++)
        Upd(1, 0, n - 1, left[i], right[i], height[i], op[i]);
    fill(finalHeight, finalHeight + n, 0);
    for (int i = 0; i < n; i++)
    {
        auto x = Get(1, 0, n - 1, i);
        cerr << i << " -> " << x.first << ' ' << x.second << '\n';
        if (x.first == -1 && x.second == -1)
            continue;
        if (x.first != -1 && x.second != -1)
        {
            if (finalHeight[i] <= x.first)
                finalHeight[i] = x.first;
            else finalHeight[i] = x.second;
            continue;
        }
        if (x.first != -1 && finalHeight[i] <= x.first)
            finalHeight[i] = x.first;
        if (x.second != -1 && finalHeight[i] > x.second)
            finalHeight[i] = x.second;
    }
    return;
}

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