Submission #500922

#	Time	Username	Problem	Language	Result	Execution time	Memory
500922		ahmeteren	Wall (IOI14_wall)	C++17	0 / 100	178 ms	9484 KiB

wall

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

using namespace std;

const int N = 4e6 + 5;

pair<int, int> seg[2 * N];

void build(int k, int l, int r)
{
    if(l == r)
    {
        seg[k] = {0, 1e9};
        return ;
    }

    int mid = (l + r) / 2;

    build(2 * k, l, mid);
    build(2 * k + 1, mid + 1, r);
    seg[k] = {0, 1e9};
}

void f(int k, int l, int r, int flag, int val)
{
    if(flag == 1)
    {
        if(val >= seg[k].second)
        {
            seg[k] = {val, val};
        }
        if(val >= seg[k].first)
        {
            seg[k].first = val;
        }
    }
    else
    {
        if(val <= seg[k].first)
        {
            seg[k] = {val, val};
        }
        if(val <= seg[k].second)
        {
            seg[k].second = val;
        }
    }
}

void push(int k, int l, int r)
{
    int mid = (l + r) / 2;

    if(seg[k].first != 0)
    {
        f(2 * k, l, mid, 1, seg[k].first);
        f(2 * k + 1, mid + 1, r, 1, seg[k].first);
    }
    if(seg[k].second != 1e9)
    {
        f(2 * k, l, mid, 2, seg[k].second);
        f(2 * k + 1, mid + 1, r, 2, seg[k].second);
    }
    seg[k] = {0, 1e9};
}

void update(int k, int l, int r, int upd_l, int upd_r, int flag, int val)
{
    if(upd_r < l or r < upd_l)
    {
        return ;
    }
    if(upd_l <= l and r <= upd_r)
    {
        f(k, l, r, flag, val);
        return ;
    }

    push(k, l, r);

    int mid = (l + r) / 2;

    update(2 * k, l, mid, upd_l, upd_r, flag, val);
    update(2 * k + 1, mid + 1, r, upd_l, upd_r, flag, val);
}

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

    int mid = (l + r) / 2;

    push(k, l, r);

    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++)
    {
        update(1, 1, n, left[i] + 1, right[i] + 1, op[i], 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:103:1: warning: control reaches end of non-void function [-Wreturn-type]
  103 | }
      | ^

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