Submission #1168752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168752		duccnamm	Wall (IOI14_wall)	C++20	100 / 100	660 ms	59108 KiB

wall

#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
#define ll int
ll n;
pair<ll,ll>f[8000006];
bool laz[8000006];
pair<ll,ll>collab(pair<ll,ll>a,pair<ll,ll>b)
{
    pair<ll,ll>c;
    c={max(a.first,b.first),min(a.second,b.second)};
    if(c.first>c.second)
	{
		if(a.first<b.first)
            return {c.first,c.first};
		return {c.second,c.second};
	}
	return c;
}
void update(ll id,ll l,ll r,ll u,ll v,ll w,ll type)
{
    if(l>v||r<u)return;
    if(l>=u&&r<=v)
    {
        if(type==1)
            f[id]=collab(f[id],{w,1e9});
        else
            f[id]=collab(f[id],{0,w});
        return;
    }
    ll mid=(l+r)/2;
    f[id*2]=collab(f[id*2],f[id]);
	f[id*2+1]=collab(f[id*2+1],f[id]);
	f[id]={0,1e9};
    update(id*2,l,mid,u,v,w,type);
    update(id*2+1,mid+1,r,u,v,w,type);
}
ll getans(ll id,ll l,ll r,ll u)
{
    if(l>u||r<u)
        return 0;
    if(l==r)
        return f[id].first;
    ll mid=(l+r)/2;
    f[id*2]=collab(f[id*2],f[id]);
	f[id*2+1]=collab(f[id*2+1],f[id]);
	f[id]={0,1e9};
	return getans(id*2,l,mid,u)+getans(id*2+1,mid+1,r,u);
}
void build(ll id,ll l,ll r)
{
    f[id]={0,1e9};
    if(l==r)
    {
        f[id]={0,0};
        return;
    }
    ll mid=(l+r)/2;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}
void buildWall(int N,int k,int op[],int left[],int right[],int height[],int finalHeight[])
{
    n=N;
    build(1,1,n);
    for(int i=0;i<k;i++)
        update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]);
    for(int i=0;i<n;i++)
        finalHeight[i]=getans(1,1,n,i+1);
    return ;
}

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