제출 #1224067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1224067		12baater	벽 (IOI14_wall)	C++20	0 / 100	284 ms	279220 KiB

wall

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

using namespace std;

const int MAXN = 2E6;
const int MAXH = 1E6 + 10;

int currentlyIn[MAXH];
int currentlyInMin[MAXH];

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    vector<queue<int>> prefixAdd(n+1);
    vector<queue<int>> prefixRem(n+1);
    vector<queue<int>> prefixAddMin(n+1);
    vector<queue<int>> prefixRemMin(n+1);
    currentlyInMin[MAXH-1] = 1E9;
    currentlyIn[0] = 1E9;
    priority_queue<int> pq;
    pq.push(0);
    for (int i = 0; i < k; i++) {
        if (op[i] == 1) {
            prefixAdd[left[i]].push(height[i]);
            prefixRem[right[i]+1].push(height[i]);
            continue;
        }
        prefixAddMin[left[i]].push(height[i]);
        prefixRemMin[right[i]+1].push(height[i]);
    }
    for (int i = 0; i < n; i++) {
        for (; !prefixRem[i].empty(); prefixRem[i].pop()) {
            int val = prefixRem[i].front();
            currentlyIn[val]--;
        }
        for (; !prefixAdd[i].empty(); prefixAdd[i].pop()) {
            int val = prefixAdd[i].front();
            if (!currentlyIn[val]) pq.push(val);
            currentlyIn[val]++;
        }
        for (; !currentlyIn[pq.top()]; pq.pop());
        finalHeight[i] = pq.top();
    }
    for (; !pq.empty(); pq.pop());
    pq.push(-(MAXH-1));

    for (int i = 0; i < n; i++) {
        for (; !prefixRemMin[i].empty(); prefixRemMin[i].pop()) {
            int val = prefixRemMin[i].front();
            currentlyInMin[val]--;
        }
        for (; !prefixAddMin[i].empty(); prefixAddMin[i].pop()) {
            int val = prefixAddMin[i].front();
            if (!currentlyInMin[val]) pq.push(-val);
            currentlyInMin[val]++;
        }
        for (; !currentlyInMin[abs(pq.top())]; pq.pop());

        finalHeight[i] = min(finalHeight[i], abs(pq.top()));
    }
    return;
}

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