Submission #500898

#	Time	Username	Problem	Language	Result	Execution time	Memory
500898		ahmeteren	Wall (IOI14_wall)	C++17	0 / 100	183 ms	9300 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"

using namespace std;

const int N = 2e6 + 5;

int seg[1 << 22], lazy_mn[1 << 22], lazy_mx[1 << 22];

void build(int k, int l, int r)
{
    lazy_mx[k] = -1e9, lazy_mn[k] = 1e9;

    if(l == r)
    {
        return ;
    }

    int mid = (l + r) / 2;

    build(2 * k, l, mid);
    build(2 * k + 1, mid + 1, r);
}

void f_mn(int k, int val)
{
    lazy_mx[k] = min(lazy_mx[k], val);
    lazy_mn[k] = min(lazy_mn[k], val);
    seg[k] = min(seg[k], val);
}

void f_mx(int k, int val)
{
    lazy_mx[k] = max(lazy_mx[k], val);
    lazy_mn[k] = max(lazy_mn[k], val);
    seg[k] = max(seg[k], val);
}

void push(int k)
{
    f_mn(2 * k, lazy_mn[k]);
    f_mn(2 * k + 1, lazy_mn[k]);
    lazy_mn[k] = 1e9;

    f_mx(2 * k, lazy_mx[k]);
    f_mx(2 * k + 1, lazy_mx[k]);
    lazy_mx[k] = -1e9;
}

void update_mn(int k, int l, int r, int upd_l, int upd_r, int val)
{
    if(upd_l <= l and r <= upd_r)
    {
        f_mn(k, val);
        return ;
    }

    push(k);

    int mid = (l + r) / 2;

    if(upd_l <= mid)
        update_mn(2 * k, l, mid, upd_l, upd_r, val);
    if(mid < upd_r)
        update_mn(2 * k + 1, mid + 1, r, upd_l, upd_r, val);
}

void update_mx(int k, int l, int r, int upd_l, int upd_r, int val)
{
    if(upd_l <= l and r <= upd_r)
    {
        f_mx(k, val);
        return ;
    }

    push(k);

    int mid = (l + r) / 2;

    if(upd_l <= mid)
        update_mx(2 * k, l, mid, upd_l, upd_r, val);
    if(mid < upd_r)
        update_mx(2 * k + 1, mid + 1, r, upd_l, upd_r, val);
}

int query(int k, int l, int r, int node)
{
    if(l == r)
    {
        return seg[k];
    }

    int mid = (l + r) / 2;

    push(k);

    if(node <= mid)
        query(2 * k, l, mid, node);
    else
        query(2 * k + 1, mid + 1, r, node);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    build(1, 1, n);

    for(int i = 0; i < k; i++)
    {
        if(op[i] == 1)
        {
            update_mx(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
        }
        else
        {
            update_mn(1, 1, n, left[i] + 1, right[i] + 1, height[i]);
        }
    }

    for(int i = 1; i <= n; i++)
    {
        finalHeight[i - 1] = query(1, 1, n, i);
    }
    return;
}

Compilation message (stderr)

wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:101:1: warning: control reaches end of non-void function [-Wreturn-type]
  101 | }
      | ^

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