Submission #30483

#	Time	Username	Problem	Language	Result	Execution time	Memory
30483		kavun	Wall (IOI14_wall)	C++14	100 / 100	909 ms	50428 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
const int rgt = (1 << 21);
const int sz = (1<<22)+5;

int u[sz], d[sz];

void combine(int id, int down, int up)
{
  d[id] = min(d[id],down);
  d[id] = max(d[id],up);
  u[id] = max(u[id],up);
  u[id] = min(u[id],down);
}

void process(int id, char mode, int h)
{
  if(mode == 'u')
    {
      d[id] = max(d[id],h);
      u[id] = max(u[id],h);
    }
  else
    {
      d[id] = min(d[id],h);
      u[id] = min(u[id],h);
    }
}


void update(int id, int l, int r, int x, int y, int h, char mode)
{
  if(x > r || y < l)
    return;
  if(x <= l && y >= r)
    {
      process(id,mode,h);
      return;
    }
  combine(2*id,d[id],u[id]);
  combine(2*id+1,d[id],u[id]);
  d[id] = sz; u[id] = 0;

  int m = (l+r)/2;
  update(2*id,l,m,x,y,h,mode);
  update(2*id+1,m+1,r,x,y,h,mode);

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i = 0; i < k; i++)
    {
      char mode = op[i] == 1 ? 'u' : 'd';
      update(1,1,rgt,left[i]+1,right[i]+1,height[i],mode);
    }

  for(int i = 1; i < rgt-1; i++)
    combine(2*i,d[i],u[i]), combine(2*i+1,d[i],u[i]);
 

  for(int i = rgt; i <= rgt+n-1; i++)
    finalHeight[i-rgt] = min(d[i],u[i]);
}

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