Submission #1155648

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155648		a.pendov	Wall (IOI14_wall)	C++20	100 / 100	801 ms	124832 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const long long MAXN=2000009;
const long long inf=LLONG_MAX;

long long max1(long long a,long long b)
{
    if(a>b)return a;
    return b;
}

long long min1(long long a,long long b)
{
    if(a<b)return a;
    return b;
}

struct node
{
    int l;
    int r;
    long long minLazy;
    long long maxLazy;
    void cons(int _l,int _r)
    {
        l=_l;
        r=_r;
        minLazy=0;
        maxLazy=inf;
    }
};

node tree[4*MAXN];

void build(int n,int l,int r)
{
    tree[n].cons(l,r);
    if(l==r)
    {
        return;
    }
    build(2*n,l,(l+r)/2);
    build(2*n+1,(l+r)/2+1,r);
}

void push_lazy(int n)
{
    if(tree[n].l==tree[n].r)return;

    if(tree[n].minLazy>tree[2*n].maxLazy)
    {
        tree[2*n].minLazy=tree[n].minLazy;
        tree[2*n].maxLazy=tree[n].minLazy;
    }
    else
    {
        tree[2*n].minLazy=max1(tree[2*n].minLazy,tree[n].minLazy);
    }

    if(tree[n].maxLazy<tree[2*n].minLazy)
    {
        tree[2*n].maxLazy=tree[n].maxLazy;
        tree[2*n].minLazy=tree[n].maxLazy;
    }
    else
    {
        tree[2*n].maxLazy=min1(tree[2*n].maxLazy,tree[n].maxLazy);
    }


    if(tree[n].minLazy>tree[2*n+1].maxLazy)
    {
        tree[2*n+1].minLazy=tree[n].minLazy;
        tree[2*n+1].maxLazy=tree[n].minLazy;
    }
    else
    {
        tree[2*n+1].minLazy=max1(tree[2*n+1].minLazy,tree[n].minLazy);
    }

    if(tree[n].maxLazy<tree[2*n+1].minLazy)
    {
        tree[2*n+1].maxLazy=tree[n].maxLazy;
        tree[2*n+1].minLazy=tree[n].maxLazy;
    }
    else
    {
        tree[2*n+1].maxLazy=min1(tree[2*n+1].maxLazy,tree[n].maxLazy);
    }

    tree[n].minLazy=0;
    tree[n].maxLazy=inf;
}

void addChange(int n,int l,int r,long long v)
{
    push_lazy(n);
    if(tree[n].l==l&&tree[n].r==r)
    {
        if(v>tree[n].maxLazy)
        {
            tree[n].minLazy=v;
            tree[n].maxLazy=v;
        }
        else
        {
            tree[n].minLazy=max1(tree[n].minLazy,v);
        }
        return;
    }

    if(tree[2*n].r<l)
    {
        addChange(2*n+1,l,r,v);
        return;
    }

    if(tree[2*n+1].l>r)
    {
        addChange(2*n,l,r,v);
        return;
    }

    addChange(2*n,l,tree[2*n].r,v);
    addChange(2*n+1,tree[2*n+1].l,r,v);
}

void remChange(int n,int l,int r,long long v)
{
    push_lazy(n);
    if(tree[n].l==l&&tree[n].r==r)
    {
        if(v<tree[n].minLazy)
        {
            tree[n].maxLazy=v;
            tree[n].minLazy=v;
        }
        else
        {
            tree[n].maxLazy=min1(tree[n].maxLazy,v);
        }
        return;
    }

    if(tree[2*n].r<l)
    {
        remChange(2*n+1,l,r,v);
        return;
    }

    if(tree[2*n+1].l>r)
    {
        remChange(2*n,l,r,v);
        return;
    }

    remChange(2*n,l,tree[2*n].r,v);
    remChange(2*n+1,tree[2*n+1].l,r,v);
}

long long getAns(int n,int t)
{
    push_lazy(n);
    if(tree[n].l==tree[n].r)
    {
        return tree[n].minLazy;
    }

    if(tree[2*n].r<t)
    {
        return getAns(2*n+1,t);
    }

    if(tree[2*n+1].l>t)
    {
        return getAns(2*n,t);
    }

    return -1;
}

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

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

    for(int i=0;i<n;i++)
    {
        finalHeight[i]=getAns(1,i);
    }
}

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