Submission #1062866

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062866		andrei_iorgulescu	Wall (IOI14_wall)	C++14	24 / 100	321 ms	11604 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#warning That's not FB, that's my FB

using namespace std;

vector<int> lol;

struct node
{
    int mn = 0, mx = 1e9;
};

node aint[8000005];

void prop(int nod, int l, int r)
{
    if (l == r)
        return;
    aint[2 * nod].mx = min(aint[2 * nod].mx, aint[nod].mx);
    aint[2 * nod + 1].mx = min(aint[2 * nod + 1].mx, aint[nod].mx);
    aint[2 * nod].mn = max(aint[2 * nod].mn, aint[nod].mn);
    aint[2 * nod + 1].mn = max(aint[2 * nod + 1].mn, aint[nod].mn);
    if (aint[2 * nod].mn > aint[2 * nod].mx)
    {
        if (aint[nod].mx > aint[2 * nod].mn)
            aint[2 * nod].mx = aint[2 * nod].mn;
        else
            aint[2 * nod].mn = aint[2 * nod].mx;
    }
    if (aint[2 * nod + 1].mn > aint[2 * nod + 1].mx)
    {
        if (aint[nod].mx > aint[2 * nod + 1].mn)
            aint[2 * nod + 1].mx = aint[2 * nod + 1].mn;
        else
            aint[2 * nod + 1].mn = aint[2 * nod + 1].mx;
    }
    aint[nod].mn = 0;
    aint[nod].mx = 1e9;
}

void update(int nod, int l, int r, int st, int dr, int tip, int h)
{
    if (r < st or dr < l)
        return;
    prop(nod,l,r);
    if (st <= l and r <= dr)
    {
        if (tip == 1)
        {
            aint[nod].mn = max(aint[nod].mn,h);
            aint[nod].mx = max(aint[nod].mx,h);
        }
        else
        {
            aint[nod].mn = min(aint[nod].mn,h);
            aint[nod].mx = min(aint[nod].mx,h);
        }
        return;
    }
    int mij = (l + r) / 2;
    update(2 * nod,l,mij,st,dr,tip,h);
    update(2 * nod + 1,mij + 1,r,st,dr,tip,h);
}

void dfs(int nod, int l, int r)
{
    if (l == r)
        lol[l - 1] = aint[nod].mn;
    else
    {
        prop(nod,l,r);
        int mij = (l + r) / 2;
        dfs(2 * nod,l,mij);
        dfs(2 * nod + 1,mij + 1,r);
    }
}

void buildWall (int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    lol.resize(n);
    for (int i = 0; i < k; i++)
    {
        left[i]++;
        right[i]++;
        update(1,1,n,left[i],right[i],op[i],height[i]);
    }
    dfs(1,1,n);
    for (int i = 0; i < n; i++)
        finalHeight[i] = lol[i];
}

Compilation message (stderr)

wall.cpp:3:2: warning: #warning That's not FB, that's my FB [-Wcpp]
    3 | #warning That's not FB, that's my FB
      |  ^~~~~~~

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