oj.uz

Submission #788101

# Submission time Handle Problem Language Result Execution time Memory
788101 2023-07-19T18:31:59 Z JoenPoenMan Wall (IOI14_wall) C++17
0 / 100
 1 ms 212 KB 

#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], 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -