Submission #280068

#	Time	Username	Problem	Language	Result	Execution time	Memory
280068		SamAnd	Wall (IOI14_wall)	C++17	0 / 100	299 ms	162948 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 2000006;

vector<int> v[N];
int op[N], height[N];

struct ban
{
    int l, r;
    int u;
    ban()
    {
        l = 0;
        r = N;
        u = -1;
    }
    ban(int ty, int h)
    {
        if (ty == 1)
        {
            l = h;
            r = N;
            u = -1;
        }
        else
        {
            l = 0;
            r = h;
            u = -1;
        }
    }
    ban(int l, int r, int u)
    {
        this->l = l;
        this->r = r;
        this->u = u;
    }
};

ban t[N * 4];

ban mer(const ban& l, const ban& r)
{
    if (r.u != -1)
        return r;
    if (l.u != -1)
    {
        if (r.l <= l.u && l.u <= r.r)
            return l;
        if (l.u < r.l)
            return ban(-1, -1, r.l);
        return ban(-1, -1, r.r);
    }
    if (l.l > r.r)
        return ban(-1, -1, r.r);
    if (l.r < r.l)
        return ban(-1, -1, r.l);
    return ban(max(l.l, r.l), min(l.r, r.r), -1);
}

void ubd(int tl, int tr, int x, bool z, int pos)
{
    if (tl == tr)
    {
        if (z)
            t[pos] = ban(op[x], height[x]);
        else
            t[pos] = ban();
        return;
    }
    int m = (tl + tr) / 2;
    if (x <= m)
        ubd(tl, m, x, z, pos * 2);
    else
        ubd(m + 1, tr, x, z, pos * 2 + 1);
    t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for (int i = 0; i < k; ++i)
    {
        ::op[i] = op[i];
        ::height[i] = height[i];
        v[left[i]].push_back(i + 1);
        v[right[i] + 1].push_back(-i - 1);
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < sz(v[i]); ++j)
        {
            int x = v[i][j];
            if (x > 0)
            {
                ubd(0, n - 1, x - 1, true, 1);
            }
            else
            {
                ubd(0, n - 1, -x - 1, false, 1);
            }
        }
        if (t[1].u != -1)
            finalHeight[i] = t[1].u;
        else
        {
            if (t[1].l <= 0 && 0 <= t[1].r)
                finalHeight[i] = 0;
            else
                finalHeight[i] = t[1].l;
        }
    }
}

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