Submission #226440

#	Time	Username	Problem	Language	Result	Execution time	Memory
226440		a_player	Wall (IOI14_wall)	C++14	61 / 100	739 ms	16504 KiB

wall

#include "wall.h"
#ifdef ALE
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define lo first
#define hi second

const int nax=2e6+6;
const int inf=INT_MAX;

pair<int,int> rt[2*nax];

void merge(pair<int,int> a, pair<int,int>& b){
  int oldhi=b.hi;
  b.lo=max(a.lo,b.lo);
  b.hi=min(a.hi,b.hi);
  if(oldhi<a.lo)b.hi=b.lo;
  else if(a.hi<b.lo)b.lo=b.hi;
}

void pre(int k, int x, int y){
  if(x!=y){
      merge(rt[k],rt[2*k]);
      merge(rt[k],rt[2*k+1]);
      rt[k]={0,inf};
  }
}

void update(int k, int a, int b, int x, int y, int mval,int Mval){
  pre(k,x,y);
  if(x>b||y<a)return;
  if(x>=a&&y<=b){
    merge({mval,Mval},rt[k]);
    return;
  }
  int m=(x+y)/2;
  update(2*k,a,b,x,m,mval,Mval);
  update(2*k+1,a,b,m+1,y,mval,Mval);
}
void solve(int k, int x, int y, int* f){
  pre(k,x,y);
  if(x>y)return;
  if(x==y){
    f[x]=rt[k].lo;
    return;
  }
  int m=(x+y)/2;
  solve(2*k,x,m,f);
  solve(2*k+1,m+1,y,f);

}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<4*nax;i++)rt[k]={0,inf};
      for(int i=0;i<k;i++){
        if(op[i]==1)update(1,left[i],right[i],0,n-1,height[i],inf);
        else update(1,left[i],right[i],0,n-1,0,height[i]);
      }
      solve(1,0,n-1,finalHeight);
}

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