oj.uz

Submission #788105

# Submission time Handle Problem Language Result Execution time Memory
788105 2023-07-19T18:39:30 Z JoenPoenMan Wall (IOI14_wall) C++17
8 / 100
 3000 ms 30864 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]+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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 115 ms 844 KB Output is correct
3 Correct 40 ms 468 KB Output is correct
4 Correct 352 ms 852 KB Output is correct
5 Correct 456 ms 1008 KB Output is correct
6 Correct 463 ms 884 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Execution timed out 3050 ms 30864 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 112 ms 896 KB Output is correct
3 Correct 40 ms 468 KB Output is correct
4 Correct 353 ms 884 KB Output is correct
5 Correct 458 ms 892 KB Output is correct
6 Correct 469 ms 892 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Execution timed out 3075 ms 30756 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 118 ms 868 KB Output is correct
3 Correct 40 ms 468 KB Output is correct
4 Correct 349 ms 928 KB Output is correct
5 Correct 481 ms 888 KB Output is correct
6 Correct 452 ms 976 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Execution timed out 3058 ms 30836 KB Time limit exceeded
9 Halted 0 ms 0 KB -