Submission #500937

#	Time	Username	Problem	Language	Result	Execution time	Memory
500937		ahmeteren	Wall (IOI14_wall)	C++17	100 / 100	1355 ms	75628 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
 
using namespace std;
 
const int N = 2e6 + 5;
 
int seg[5 * N], lazy_mn[5 * N], lazy_mx[5 * N];
 
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_r < l or r < upd_l)
        return ;
    if(upd_l <= l and r <= upd_r)
    {
        f_mn(k, val);
        return ;
    }
 
    push(k);
 
    int mid = (l + r) / 2;
 
    update_mn(2 * k, l, mid, upd_l, upd_r, val);
    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_r < l or r < upd_l)
        return ;
    if(upd_l <= l and r <= upd_r)
    {
        f_mx(k, val);
        return ;
    }
 
    push(k);
 
    int mid = (l + r) / 2;
 
    update_mx(2 * k, l, mid, upd_l, upd_r, val);
    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)
        return query(2 * k, l, mid, node);
    else
        return 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;
}

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