Submission #1147703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147703		brianhdzmdo	Wall (IOI14_wall)	C++20	24 / 100	374 ms	14004 KiB

wall

#include <algorithm>
#include <cmath>
#include <iostream>
#include <math.h>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <utility>
#include <vector>
#include <climits>

using namespace std;

const int N = 2000005;
const int INF = 1000000000;

int ST[4 * N];
int lazyMax[4 * N], lazyMin[4 * N];

void init(int n) 
{
    int size = 4 * n;
    for (int i = 0; i < size; i++) 
    {
        ST[i] = 0;
        lazyMax[i] = -1;
        lazyMin[i] = INF;
    }
}

void propagate(int node, int l, int r) 
{
    if (lazyMax[node] != -1) 
    {
        ST[node] = max(lazyMax[node], ST[node]);
        if (l != r) 
        {
            int left = node * 2 + 1;
            int right = node * 2 + 2;
            lazyMax[left] = max(lazyMax[left], lazyMax[node]);
            lazyMax[right] = max(lazyMax[right], lazyMax[node]);
        }
        lazyMax[node] = -1;
    }
    if (lazyMin[node] != INF) 
    {
        ST[node] = min(lazyMin[node], ST[node]);
        if (l != r) 
        {
            int left = node * 2 + 1;
            int right = node * 2 + 2;
            lazyMin[left] = min(lazyMin[left], lazyMin[node]);
            lazyMin[right] = min(lazyMin[right], lazyMin[node]);
        }
        lazyMin[node] = INF;
    }
}

void updateMax(int node, int l, int r, int a, int b, int h) 
{
    propagate(node, l, r);
    if (l > b || r < a) 
    {
        return;
    }
    if (a <= l && r <= b) 
    {
        lazyMax[node] = max(lazyMax[node], h);
        propagate(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2 + 1;
    int right = node * 2 + 2;
    updateMax(left, l, mid, a, b, h);
    updateMax(right, mid + 1, r, a, b, h);
    ST[node] = max(ST[left], ST[right]);
}

void updateMin(int node, int l, int r, int a, int b, int h) 
{
    propagate(node, l, r);
    if (l > b || r < a) 
    {
        return;
    }
    if (a <= l && r <= b) 
    {
        lazyMin[node] = min(lazyMin[node], h);
        propagate(node, l, r);
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2 + 1;
    int right = node * 2 + 2;
    updateMin(left, l, mid, a, b, h);
    updateMin(right, mid + 1, r, a, b, h);
    ST[node] = min(ST[left], ST[right]);
}

int query(int node, int l, int r, int pos) 
{
    propagate(node, l, r);
    if (l == r) 
    {
        return ST[node];
    }
    int mid = (l + r) / 2;
    int left = node * 2 + 1;
    int right = node * 2 + 2;
    if (pos <= mid) 
    {
        return query(left, l, mid, pos);
    } 
    else 
    {
        return query(right, mid + 1, r, pos);
    }
}

void buildWall(int n, int k, int op[], int leftArr[], int rightArr[], int height[], int finalHeight[]) 
{
    init(n);
    for (int i = 0; i < k; i++) 
    {
        int a = leftArr[i];
        int b = rightArr[i];
        int h = height[i];
        if (op[i] == 1) 
        {
            updateMax(0, 0, n - 1, a, b, h);
        } 
        else 
        {
            updateMin(0, 0, n - 1, a, b, h);
        }
    }
    for (int i = 0; i < n; i++) 
    {
        finalHeight[i] = query(0, 0, n - 1, i);
    }
}

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