Submission #1224083

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224083		12baater	Wall (IOI14_wall)	C++20	0 / 100	249 ms	43248 KiB

wall

#include "wall.h"
#include <iostream>
#include <vector>
#include <set>
#include <queue>

using namespace std;
const int MAXN = 2E6;
const int MAXH = 1E6 + 10;


void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    vector<pair<int, pair<int,int>>> fp;
    multiset<int> big;
    multiset<int> small;
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            fp.push_back({left[i],{height[i],1}});
            fp.push_back({right[i]+1,{-height[i],1}});
            continue;
        }
        fp.push_back({left[i],{height[i],0}});
        fp.push_back({right[i]+1,{-height[i],0}});
    }
    sort(fp.begin(),fp.end());
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (fp[j].first <= i && j < fp.size()) {
            auto [val, type] = fp[j].second;
            if (type == 1) {
                if (val >= 0) {
                    big.insert(val);
                } else {
                    big.erase(-val);
                }
            } else {
                if (val >= 0) {
                    small.insert(val);
                } else {
                    small.erase(-val);
                }
            }
            j++;
        }
        if (!big.empty())
            finalHeight[i] = *prev(big.end());

        if (!small.empty())
            finalHeight[i] = min(finalHeight[i], *small.begin());

    }
    return;
}

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