Submission #572535

#	Time	Username	Problem	Language	Result	Execution time	Memory
572535		LunaMeme	Wall (IOI14_wall)	C++14	0 / 100	202 ms	25516 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
typedef pair<int, int> ii;
typedef vector<pair<int, int>> vii;
typedef vector<int> vi;
typedef long long ll;
#define PB push_back
#define MP make_pair
#define FOR(i, x, y) for (int i = x; i < y ; i ++)

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
    vector<pair<int,ii>> phases;
    int num_add = 0;
    while(num_add < k && op[num_add] == 1 ){
        phases.PB(MP(left[num_add], MP(height[num_add], right[num_add])));
        num_add ++;
    }
    sort(phases.begin(), phases.end());
    int i_phase = 0;
    priority_queue<ii> ranges; // (height, right)
    vi arr(n, 0);
    FOR(i, 0, n){
        while(i_phase < num_add && i == phases[i_phase].first){
            ranges.push(phases[i_phase].second);
            i_phase ++;
        }
        while(!ranges.empty() && ranges.top().second < i){
            ranges.pop();
        }
        if (ranges.empty()) arr[i] = 0;
        else arr[i] = ranges.top().first;
    }
    phases.clear();
    FOR(i, num_add + 1, k){
        phases.PB(MP(left[i], MP(-height[i], right[i])));
    }
    sort(phases.begin(), phases.end());
    priority_queue<ii> Ranges; // (height, right)
    i_phase = 0;
    FOR(i, 0, n){
        while(i_phase < (k -num_add) && i == phases[i_phase].first){
            Ranges.push(phases[i_phase].second);
            i_phase ++;
        }
        while(!Ranges.empty() && Ranges.top().second < i){
            Ranges.pop();
        }
        if (!Ranges.empty()) arr[i] = min(arr[i], -Ranges.top().first);
    }
    FOR(i, 0, n){
        finalHeight[i] = arr[i];
    }
}

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