Submission #243168

#	Time	Username	Problem	Language	Result	Execution time	Memory
243168		Kubin	Wall (IOI14_wall)	C++17	100 / 100	986 ms	59388 KiB

wall

#include <bits/stdc++.h>

using namespace std;

struct clamp_op
{
    int a, b;
    int operator() (int x)
    {
        return min(max(x, a), b);
    }
} clamp_id = {INT_MIN, INT_MAX};

clamp_op operator>> (clamp_op F, clamp_op G)
{
    if(F.b < G.a)
        return {G.a, G.a};
    else if(G.b < F.a)
        return {G.b, G.b};
    else
        return {max(F.a, G.a), min(F.b, G.b)};
}
clamp_op& operator>>= (clamp_op& F, clamp_op G)
{
    return F = F >> G;
}
ostream& operator<< (ostream& out, clamp_op F)
{
    return out << "clamp_op{" << F.a << ", " << F.b << "}";
}

struct segment_tree
{
    size_t w;
    vector<clamp_op> values;

    segment_tree(size_t n) : w(1 << __lg(2*n - 1)), values(2*w, clamp_id) {}

    void push(size_t i)
    {
        if(i < w)
        {
            values[2*i+0] >>= values[i];
            values[2*i+1] >>= values[i];
            values[i] = clamp_id;
        }
    }

    void mut(size_t i, size_t nodeL, size_t nodeR, size_t L, size_t R, clamp_op F)
    {
        push(i);
        if(nodeR < L or R < nodeL)
            return;
        else if(L <= nodeL and nodeR <= R)
            values[i] >>= F;
        else
            mut(2*i+0, nodeL, (nodeL+nodeR)/2, L, R, F),
            mut(2*i+1, (nodeL+nodeR)/2+1, nodeR, L, R, F);
    }

    void mut(size_t L, size_t R, clamp_op F)
    {
        return mut(1, 0, w-1, L, R, F);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int out[])
{
    segment_tree tree(n);
    for(int i = 0; i < k; i++)
    {
        auto f = op[i] == 1 ? clamp_op{height[i], INT_MAX} : clamp_op{INT_MIN, height[i]};
        tree.mut(left[i], right[i], f);
    }
    for(int i = 1; i < (int)tree.w; i++)
        tree.push(i);
    for(int i = 0; i < n; i++)
        out[i] = tree.values[tree.w + i](0);
}

#ifdef XHOVA
int main()
{
    int out[10];
    int op[] = {1, 2, 2, 1, 1, 2}, left[] = {1, 4, 3, 0, 2, 6}, right[] = {8, 9, 6, 5, 2, 7}, height[] = {4, 1, 5, 3, 5, 0};
    buildWall(10, 6, op, left, right, height, out);
    for(auto x : out)
        cout << x << " ";
    cout << endl;
}
#endif

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