oj.uz

Submission #788137

# Submission time Handle Problem Language Result Execution time Memory
788137 2023-07-19T20:02:29 Z JoenPoenMan Wall (IOI14_wall) C++17
24 / 100
 495 ms 47464 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, 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.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 482 ms 47464 KB Output is correct
3 Correct 181 ms 18296 KB Output is correct
4 Correct 495 ms 43192 KB Output is correct
5 Correct 274 ms 36000 KB Output is correct
6 Correct 260 ms 38212 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Incorrect 3 ms 680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

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