Submission #218893

#	Time	Username	Problem	Language	Result	Execution time	Memory
218893		dung11112003	Wall (IOI14_wall)	C++11	100 / 100	834 ms	99664 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxN = 2e6 + 10;
const int inf = 1e9;

struct node
{
    int mi, ma;
    node() : mi(0), ma(0) {}
    node(int mi, int ma) : mi(mi), ma(ma) {}
} f[maxN * 4];
int L, R, val;
int *ans;

void down(int x)
{
    uin(f[x * 2 + 1].mi, f[x].mi);
    uin(f[x * 2 + 1].ma, f[x * 2 + 1].mi);
    uax(f[x * 2 + 1].ma, f[x].ma);
    uax(f[x * 2 + 1].mi, f[x * 2 + 1].ma);
    uin(f[x * 2 + 2].mi, f[x].mi);
    uin(f[x * 2 + 2].ma, f[x * 2 + 2].mi);
    uax(f[x * 2 + 2].ma, f[x].ma);
    uax(f[x * 2 + 2].mi, f[x * 2 + 2].ma);
}

void minimize(int x, int lo, int hi)
{
    if (lo > R || hi < L)
    {
        return;
    }
    if (lo >= L && hi <= R)
    {
        uin(f[x].mi, val);
        uin(f[x].ma, f[x].mi);
        return;
    }
    down(x);
    int mid = (lo + hi) / 2;
    minimize(x * 2 + 1, lo, mid);
    minimize(x * 2 + 2, mid + 1, hi);
    f[x].mi = max(f[x * 2 + 1].mi, f[x * 2 + 2].mi);
    f[x].ma = min(f[x * 2 + 1].ma, f[x * 2 + 2].ma);
}

void maximize(int x, int lo, int hi)
{
    if (lo > R || hi < L)
    {
        return;
    }
    if (lo >= L && hi <= R)
    {
        uax(f[x].ma, val);
        uax(f[x].mi, f[x].ma);
        return;
    }
    down(x);
    int mid = (lo + hi) / 2;
    maximize(x * 2 + 1, lo, mid);
    maximize(x * 2 + 2, mid + 1, hi);
    f[x].mi = max(f[x * 2 + 1].mi, f[x * 2 + 2].mi);
    f[x].ma = min(f[x * 2 + 1].ma, f[x * 2 + 2].ma);
}

void build(int x, int lo, int hi)
{
    if (lo == hi)
    {
        ans[lo] = f[x].mi;
        return;
    }
    down(x);
    int mid = (lo + hi) / 2;
    build(x * 2 + 1, lo, mid);
    build(x * 2 + 2, mid + 1, hi);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for0(i, k)
    {
        if (op[i] == 1)
        {
            //adding phase
            L = left[i], R = right[i], val = height[i];
            maximize(0, 0, n - 1);
        }
        else
        {
            //removing phase
            L = left[i], R = right[i], val = height[i];
            minimize(0, 0, n - 1);
        }
    }
    ans = finalHeight;
    build(0, 0, n - 1);
}

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