Submission #742186

#	Time	Username	Problem	Language	Result	Execution time	Memory
742186		vjudge1	Wall (IOI14_wall)	C++17	100 / 100	731 ms	69580 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int INF=INT_MAX;
const int t=(1<<21);

pair<int, int> tree[2*t-1];

void propagate(int x)
{
    if (2*x+2>=2*t-1)
        return;

    tree[2*x+1].first=min(tree[2*x+1].first, tree[x].first);
    tree[2*x+1].second=min(tree[2*x+1].second, tree[2*x+1].first);
    tree[2*x+1].second=max(tree[2*x+1].second, tree[x].second);
    tree[2*x+1].first=max(tree[2*x+1].first, tree[2*x+1].second);

    tree[2*x+2].first=min(tree[2*x+2].first, tree[x].first);
    tree[2*x+2].second=min(tree[2*x+2].second, tree[2*x+2].first);
    tree[2*x+2].second=max(tree[2*x+2].second, tree[x].second);
    tree[2*x+2].first=max(tree[2*x+2].first, tree[2*x+2].second);

    tree[x]={INF, -INF};

    return;
}

void adding(int x, int l, int r, int lt, int rt, int value)
{
    if (r<=lt || l>=rt)
        return;

    propagate(x);

    if (l>=lt && r<=rt)
    {
        tree[x].second=max(tree[x].second, value);
        tree[x].first=max(tree[x].first, tree[x].second);

        return;
    }

    adding(2*x+1, l, (l+r)/2, lt, rt, value);
    adding(2*x+2, (l+r)/2, r, lt, rt, value);

    return;
}

void removing(int x, int l, int r, int lt, int rt, int value)
{
    if (r<=lt || l>=rt)
        return;

    propagate(x);

    if (l>=lt && r<=rt)
    {
        tree[x].first=min(tree[x].first, value);
        tree[x].second=min(tree[x].second, tree[x].first);

        return;
    }

    removing(2*x+1, l, (l+r)/2, lt, rt, value);
    removing(2*x+2, (l+r)/2, r, lt, rt, value);

    return;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for (int i=0; i<2*t-1; i++)
        tree[i]={INF, -INF};
    for (int i=0; i<k; i++)
    {
        if (op[i]==1)
            adding(0, 0, t, left[i], right[i]+1, height[i]);
        if (op[i]==2)
            removing(0, 0, t, left[i], right[i]+1, height[i]);
    }
    for (int i=0; i<2*t-1; i++)
        propagate(i);
    for (int i=0; i<n; i++)
        finalHeight[i]=max(tree[i+t-1].second, 0);

    return;
}

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