Submission #600409

#	Time	Username	Problem	Language	Result	Execution time	Memory
600409		PiejanVDC	Wall (IOI14_wall)	C++17	0 / 100	124 ms	262144 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

/*
minA = min(min1, min2)
minA = max(minA, max2)
maxA = max(max1, max2)
maxA = min(maxA, min2)
*/

const int mxN = (int)4e7+5;

vector<int>mn(mxN, INT_MAX);
vector<int>mx(mxN, INT_MIN);

int l,r;
int MX, MN;

void reset(int p) {
    mn[p] = INT_MAX;
    mx[p] = INT_MIN;
}

void push(int mn_, int mx_, int p) {
    mn[p] = min(mn[p], mn_);
    mn[p] = max(mn[p], mx_);
    mx[p] = max(mx[p], mx_);
    mx[p] = min(mx[p], mn_);
}

void update(int i, int j, int p) {
    if(i > r || j < l)
        return;
    if(i >= l && j <= r) {
        mn[p] = min(mn[p], MN);
        mn[p] = max(mn[p], MX);
        mx[p] = max(mx[p], MX);
        mx[p] = min(mx[p], MN);
        return;
    }
    int mid = (i+j)/2;
    push(mn[p], mx[p], 2*p);
    push(mn[p], mx[p], 2*p+1);
    reset(p);
    update(i, mid, 2*p);
    update(mid+1, j, 2*p+1);
}

int query(int i, int j, int p) {
    if(i >= l && j <= r) {
        return max(0, mx[p]);
    }
    int mid = (i+j)/2;
    push(mn[p], mx[p], 2*p);
    push(mn[p], mx[p], 2*p+1);
    reset(p);
    if(l <= mid)
        return query(i, mid, 2*p);
    return query(mid+1, j, 2*p+1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for(int i = 0 ; i < k ; i++) {
        if(op[i] == 1) {
            MX = height[i];
            MN = INT_MAX;
            l = left[i];
            r = right[i];
            update(0, n-1, 1);
        } else {
            MX = INT_MIN;
            MN = height[i];
            l = left[i];
            r = right[i];
            update(0, n-1, 1);
        }
    }
    for(int i = 0 ; i < n ; i++) {
        l = i, r = i;
        finalHeight[i] = query(0, n-1, 1);
    }
}

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