Submission #249531

#	Time	Username	Problem	Language	Result	Execution time	Memory
249531		hhh07	Wall (IOI14_wall)	C++14	100 / 100	743 ms	69712 KiB

wall

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <utility>
#include <set>
#include <cmath>
#include <climits>
#include <cstring>
 
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;

const int N = 1<<21;
int a[2*N + 5], b[2*N + 5];

void updateChild(int curr, int child){
    a[child] = min(a[child], a[curr]);
    a[child] = max(a[child], b[curr]);
    b[child] = max(b[child], b[curr]);
    b[child] = min(b[child], a[curr]);
}

void updateSeg(int curr, int l, int r, int beg, int end, int type, int h){
    if (l > end || r < beg)
        return;

    if (l >= beg && r <= end){
        if (!type){
            a[curr] = max(a[curr], h);
            b[curr] = max(b[curr], h);
        }
        else{
            b[curr] = min(b[curr], h);
            a[curr] = min(a[curr], h);
        }
        return;
    }
    updateChild(curr, 2*curr + 1);
    updateChild(curr, 2*curr + 2);
    a[curr] = N; b[curr] = 0;
    
    int mid = (l + r)/2;
    
    updateSeg(2*curr + 1, l, mid, beg, end, type, h);
    updateSeg(2*curr + 2, mid + 1, r, beg, end, type, h);
}



void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    std::ios::sync_with_stdio(false);
    for (int i = 0; i < k; i++){ 
        updateSeg(0, 0, N - 1, left[i], right[i], op[i] - 1, height[i]);
    }
    for (int i = 0; i < N - 1; i++){
        updateChild(i, 2*i + 1);
        updateChild(i, 2*i + 2);
    }
    
    for (int i = N - 1; i < N + n - 1; i++)
        finalHeight[i - (N - 1)] = min(a[i], b[i]);
    
    
}

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