Submission #788105

#	Time	Username	Problem	Language	Result	Execution time	Memory
788105		JoenPoenMan	Wall (IOI14_wall)	C++17	8 / 100	3075 ms	30864 KiB

wall

#include <bits/stdc++.h>
#define ALL(arr) begin(arr), end(arr)

using namespace std;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    // x, ind, end, adding, height
    vector<tuple<int, int, bool, bool, int>> actions;
    for (int i = 0; i < k; i++) {
        actions.push_back({left[i], i, false, (op[i] == 1), height[i]});
        actions.push_back({right[i]+1, i, true, (op[i] == 1), height[i]});
    }
    sort(ALL(actions));
    int px = 0;
    multiset<tuple<int, bool, int>> active;
    vector<int> heights;
    heights.push_back(0);
    for (auto [x, ind, end, add, goalheight] : actions) {
        for (int j = px; j < x; j++) {
            finalHeight[j] = heights.back();
        }
        px = x;
        if (end) {
            auto it = active.find({ind, add, goalheight});
            int tmph = heights[distance(active.begin(), it)];
            heights.erase(heights.begin() + distance(active.begin(), it)+1);
            int dis = distance(active.begin(), it);
            active.erase(it);
            it = next(active.begin(), dis);
            for (; it != active.end(); it++) {
                auto [ind, add, height] = *it;
                int newh = (add ? max(height, tmph) : min(height, tmph));
                if (newh != heights[distance(active.begin(), it)+1]) {
                    heights[distance(active.begin(), it)+1] = newh;
                    tmph = newh;
                    continue;
                }
                break;
            }
        } else {
            active.insert({ind, add, goalheight});
            auto it = active.find({ind, add, goalheight});
            int tmph = heights[distance(active.begin(), it)];
            bool first = true;
            for (; it != active.end(); it++) {
                auto [ind, add, height] = *it;
                int newh = (add ? max(height, tmph) : min(height, tmph));
                if (first || newh != heights[distance(active.begin(), it)+1]) {
                    if (first) {
                        first = false;
                	    heights.insert(heights.begin() + distance(active.begin(), it) + 1, newh);
                    } else {
                        heights[distance(active.begin(), it) + 1] = newh;
                    }
                    tmph = newh;
                    continue;
                }
                break;
            }
        }
    }
    for (int j = px; j < n; j++) {
        finalHeight[j] = 0;
    }
    return;
}

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