Submission #1111117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111117		TheGreatAntivirus	Wall (IOI14_wall)	C++17	100 / 100	942 ms	69596 KiB

wall

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

using namespace std;

const int MAXN = (1 << 21);

struct query
{
    int mx, mn;
    query()
    {
        mx = 0; mn = 1e9;
    }
};

query sg[2 * MAXN];

class segment
{
    public:
        void push(int v, int vl, int vr)
        {
            if(vl != vr)
            {
                sg[2 * v].mx = min(sg[v].mn, max(sg[v].mx, sg[2 * v].mx));
                sg[2 * v + 1].mx = min(sg[v].mn, max(sg[v].mx, sg[2 * v + 1].mx));
                sg[2 * v].mn = max(sg[v].mx, min(sg[v].mn, sg[2 * v].mn));
                sg[2 * v + 1].mn = max(sg[v].mx, min(sg[v].mn, sg[2 * v + 1].mn));
                sg[v].mn = 1e9;
                sg[v].mx = 0;
            }
        }
        void upd(int v, int vl, int vr, int l, int r, int val, int m)
        {
            if(vl > r || vr < l)
            {
                return;
            }
            push(v, vl, vr);
            if(l <= vl && vr <= r)
            {
                if(m == 1)
                {
                    sg[v].mx = max(sg[v].mx, val);
                    sg[v].mn = max(sg[v].mn, sg[v].mx);
                }
                else
                {
                    sg[v].mn = min(sg[v].mn, val);
                    sg[v].mx = min(sg[v].mx, sg[v].mn);
                }
                push(v, vl, vr);
                return;
            }
            int mid = (vl + vr) / 2;
            upd(2 * v, vl, mid, l, r, val, m);
            upd(2 * v + 1, mid + 1, vr, l, r, val, m);
        }
        query get(int v, int vl, int vr, int p)
        {
            if(vl > p || vr < p)
            {
                query tmp;
                return tmp;
            }
            push(v, vl, vr);
            if(vl == vr && vl == p)
            {
                return sg[v];
            }
            int mid = (vl + vr) / 2;
            query lc = get(2 * v, vl, mid, p),
                  rc = get(2 * v + 1, mid + 1, vr, p);
            query res; res.mn = min(lc.mn, rc.mn);
            res.mx = max(lc.mx, rc.mx);
            return res;
        }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	segment s;
    for(int i = 0; i < k; i++)
    {
        s.upd(1, 0, MAXN - 1, left[i], right[i], height[i], op[i]);
    }
    for(int i = 0; i < n; i++)
    {
        query ans = s.get(1, 0, MAXN - 1, i);
        finalHeight[i] = min(ans.mx, ans.mn);
    }
}

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