Submission #524741

#	Time	Username	Problem	Language	Result	Execution time	Memory
524741		abdzag	Wall (IOI14_wall)	C++17	0 / 100	197 ms	8100 KiB

wall

#include <bits/stdc++.h>

typedef long long ll;
const long long inf = 2e9;
using namespace std;

struct Node
{
    Node *l = 0, *r = 0;
    int lo, hi;
    int max_of_interval = inf, min_of_interval = -inf; // Allowed max and allowed min of intervals
    Node(int lo, int hi) : lo(lo), hi(hi)
    {
        if (lo + 1 < hi)
        {
            int mid = lo + (hi - lo) / 2;
            l = new Node(lo, mid);
            r = new Node(mid, hi);
        }
    }
    ~Node()
    {
        delete l;
        delete r;
    }
    int query(int pos)
    {
        if (lo + 1 == hi)
            return min_of_interval == -inf ? 0 : min_of_interval;
        push();
        int mid = lo + (hi - lo) / 2;
        if (pos < mid)
            return l->query(pos);
        return r->query(pos);
    }
    void minimize(int L, int R, int X)
    {
        if (R <= lo || hi <= L)
            return;
        if (L <= lo && hi <= R)
        {
            max_of_interval = min(X, max_of_interval);
            min_of_interval = min(X, min_of_interval);
            return;
        }
        push();
        l->minimize(L, R, X);
        r->minimize(L, R, X);
    }
    void maximize(int L, int R, int X)
    {
        if (R <= lo || hi <= L)
            return;
        if (L <= lo && hi <= R)
        {
            min_of_interval = max(X, min_of_interval);
            max_of_interval = max(max_of_interval, min_of_interval);
            return;
        }
        push();
        l->maximize(L, R, X);
        r->maximize(L, R, X);
    }
    void push()
    {
        l->minimize(lo, hi, max_of_interval);
        r->minimize(lo, hi, max_of_interval);
        l->maximize(lo, hi, min_of_interval);
        r->maximize(lo, hi, min_of_interval);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    Node *tree = new Node(0, n);
    for (int i = 0; i < k; i++)
    {
        ll l, r, a, type;
        type = op[i];
        l = left[i];
        r = right[i];
        a = height[i];
        r++;
        type--;
        if (type)
            tree->minimize(l, r, a);
        else
            tree->maximize(l, r, a);
    }
    for (int i = 0; i < n; i++)
    {
        finalHeight[i] = tree->query(i);
    }
    delete tree;
}

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