Submission #1199417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199417		raphaelp	Wall (IOI14_wall)	C++20	100 / 100	542 ms	79156 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

class SegTree
{
private:
    int N;
    vector<int> A, B;
    int l(int x) { return (x << 1); }
    int r(int x) { return (x << 1) + 1; }

public:
    SegTree(int x)
    {
        N = pow(2, ceil(log2(x)));
        A.assign(2 * N, 0);
        B.assign(2 * N, 100000);
    }
    void update(int X, int vala, int valb)
    {
        int x = X + N;
        A[x] = vala, B[x] = valb;
        x /= 2;
        while (x)
        {
            B[x] = max(A[r(x)], min(B[l(x)], B[r(x)]));
            A[x] = min(B[x], max(A[l(x)], A[r(x)]));
            x /= 2;
        }
    }
    int PQ() { return A[1]; }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    SegTree ST(k);
    vector<vector<int>> Tab;
    for (int i = 0; i < k; i++)
    {
        int a = 0, b = height[i];
        if (op[i] == 1)
            a = height[i], b = 100000;
        Tab.push_back({left[i], i, a, b});
        Tab.push_back({right[i] + 1, i, 0, 100000});
    }
    sort(Tab.begin(), Tab.end());
    int buff = 0;
    for (int i = 0; i < n; i++)
    {
        while (buff < Tab.size() && Tab[buff][0] == i)
        {
            ST.update(Tab[buff][1], Tab[buff][2], Tab[buff][3]);
            buff++;
        }
        finalHeight[i] = ST.PQ();
    }
}

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