Submission #430788

#	Time	Username	Problem	Language	Result	Execution time	Memory
430788		TLP39	Wall (IOI14_wall)	C++14	100 / 100	835 ms	85636 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

const int INF=1000000000;

struct func{
    int l,r;
};

func compose(func f,func g)
{
    if(f.r<=g.l) return {g.l,g.l};
    if(f.l>=g.r) return {g.r,g.r};
    return {max(f.l,g.l),min(f.r,g.r)};
}

int n,k;

func seg[8000010];
bool marked[8000010],bottom[8000010];
int pos[2000010];

void build(int v,int st,int ed)
{
    marked[v]=false;
    bottom[v]=false;
    seg[v]={-INF,INF};
    if(st==ed)
    {
        pos[st]=v;
        bottom[v]=true;
        return;
    }
    int mid=(st+ed)>>1;
    build(v<<1,st,mid);
    build(1+(v<<1),mid+1,ed);
}

void push_down(int v)
{
    if(!marked[v] || bottom[v]) return;
    marked[v]=false;
    marked[v<<1]=marked[1+(v<<1)]=true;
    seg[v<<1]=compose(seg[v<<1],seg[v]);
    seg[1+(v<<1)]=compose(seg[1+(v<<1)],seg[v]);
    seg[v]={-INF,INF};
}

void upd(int v,int l,int r,int st,int ed,func f)
{
    if(st>ed) return;
    if(l==st && r==ed)
    {
        marked[v]=true;
        seg[v]=compose(seg[v],f);
        return;
    }
    push_down(v);
    int mid=(l+r)>>1;
    upd(v<<1,l,mid,st,min(mid,ed),f);
    upd(1+(v<<1),mid+1,r,max(mid+1,st),ed,f);
}

int que(int x)
{
    int ver=pos[x],res=0;
    while(ver)
    {
        if(res<=seg[ver].l) res=seg[ver].l;
        else if(res>=seg[ver].r) res=seg[ver].r;
        ver>>=1;
    }
    return res;
}

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
  n=N;
  k=K;
  build(1,0,n-1);
  for(int i=0;i<k;i++)
  {
    if(op[i]==1)
    {
        upd(1,0,n-1,left[i],right[i],{height[i],INF});
    }
    else
    {
        upd(1,0,n-1,left[i],right[i],{-INF,height[i]});
    }
  }
  for(int i=0;i<n;i++) finalHeight[i]=que(i);
  return;
}

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