Submission #1235199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235199		denislav	Wall (IOI14_wall)	C++20	100 / 100	774 ms	151604 KiB

wall

# include <iostream>
# include <climits>
//# include "grader.cpp"
# include "wall.h"
using namespace std;

const int MAX=2e6+11;

int N;
int a[MAX];

struct node
{
    int l,r;
    node() {l=0;r=INT_MAX;}
    node(int _l, int _r) {l=_l;r=_r;}

    node friend operator + (node A, node B)
    {
        A.l=max(A.l,B.l);
        A.r=max(A.l,A.r);
        A.r=min(A.r,B.r);
        A.l=min(A.l,A.r);
        return A;
    }
};

node lazy[MAX*4];
node tree[MAX*4];

void build(int v=1, int l=0, int r=N-1)
{
    if(l==r)
    {
        tree[v]={0,0};
        return ;
    }

    int mid=(l+r)/2;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
    tree[v]=tree[v*2]+tree[v*2+1];
}

void push_lazy(int v, int l, int r)
{
    if(lazy[v].l==0 and lazy[v].r==INT_MAX) return ;

    tree[v]=tree[v]+lazy[v];
    //cout<<l<<" "<<r<<":"<<tree[v].l<<" "<<tree[v].r<<"\n";
    if(l!=r)
    {
        lazy[v*2]=lazy[v*2]+lazy[v];
        lazy[v*2+1]=lazy[v*2+1]+lazy[v];
    }
    lazy[v]={0,INT_MAX};
}

void update(int le, int ri, node nd, int v=1, int l=0, int r=N-1)
{
    push_lazy(v,l,r);
    if(ri<l or r<le) return ;
    if(le<=l and r<=ri)
    {
        lazy[v]=lazy[v]+nd;
        push_lazy(v,l,r);
        return ;
    }

    int mid=(l+r)/2;
    update(le,ri,nd,v*2,l,mid);
    update(le,ri,nd,v*2+1,mid+1,r);
    tree[v]=tree[v*2]+tree[v*2+1];
}

int query(int pos, int v=1, int l=0, int r=N-1)
{
    push_lazy(v,l,r);
    if(l==r) return tree[v].l;

    int mid=(l+r)/2;
    if(pos<=mid) return query(pos,v*2,l,mid);
    else return query(pos,v*2+1,mid+1,r);
}

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

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

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

    return;
}

/**
In:
10 3
1 3 4 91220
1 5 9 48623
2 3 5 39412

Out:
0
0
0
39412
39412
39412
48623
48623
48623
48623
*/

/**
In:
10 6
1 1 8 4
2 4 9 1
2 3 6 5
1 0 5 3
1 2 2 5
2 6 7 0

Out:
3
4
5
4
3
3
0
0
1
0
*/

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