Submission #788137

#	Time	Username	Problem	Language	Result	Execution time	Memory
788137		JoenPoenMan	Wall (IOI14_wall)	C++17	24 / 100	495 ms	47464 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, int>> addactions;
    vector<tuple<int, int, bool, int>> remactions;
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            addactions.push_back({left[i], i, false, height[i]});
            addactions.push_back({right[i]+1, i, true, height[i]});
        } else {
            remactions.push_back({left[i], i, false, height[i]});
            remactions.push_back({right[i]+1, i, true, height[i]});
        }
    }
    sort(ALL(addactions));
    sort(ALL(remactions));
    int px = 0;
    multiset<int, greater<int>> prevHeights;
    prevHeights.insert(0);
    for (auto [x, ind, end, goalheight] : addactions) {
        fill(finalHeight + px, finalHeight + x, *prevHeights.begin());
        px = x;
        if (!end) {
            prevHeights.insert(goalheight);
        } else {
            auto it = prevHeights.find(goalheight);
            prevHeights.erase(it);
        }
    }
    fill(finalHeight + px, finalHeight + n, 0);
    px = 0;
    multiset<int> prevHeights2;
    prevHeights2.insert(1e8);
    int maxH = 0;
    for (auto [x, ind, end, goalheight] : remactions) {
        for (int i = px; i < x; i++) {
            maxH = finalHeight[i];
            finalHeight[i] = min(*prevHeights2.begin(), maxH);
        }
        px = x;
        if (!end) {
            prevHeights2.insert(goalheight);
        } else {
            auto it = prevHeights2.find(goalheight);
            prevHeights2.erase(it);
        }
    }
    return;
}

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