Submission #745591

#	Time	Username	Problem	Language	Result	Execution time	Memory
745591		Username4132	Wall (IOI14_wall)	C++14	0 / 100	169 ms	14104 KiB

wall

#include "wall.h"

#include<iostream>
using namespace std;
using pii = pair<int, int>;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define F first
#define S second

const int MAXN=1000010, MAXH=100010;
int n, he;

pii combine(pii a, pii b){
  if(b.S<=a.F) return {b.S - 1, b.S};
  else if(a.S<=b.F) return {b.F, b.F + 1};
  else return {max(a.F, b.F), min(a.S, b.S)};
}

pii tr[2*MAXN];

void apply(int p, pii value){
  tr[p]=combine(tr[p], value);
}

void push(int p){
  for(int s=he; s>0; --s){
    int i=(p>>s);
    apply(i<<1, tr[i]);
    apply(i<<1|1, tr[i]);
    tr[i]={0, MAXH};
  }
}

void modify(int l, int r, pii value){
  l+=n, r+=n;
  push(l);
  push(r-1);
  for(; l<r; l>>=1, r>>=1){
    if(l&1) apply(l++, value);
    if(r&1) apply(--r, value);
  }
}

void buildWall(int N, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  n=N; he=8*sizeof(int) - __builtin_clz(n);
  forn(i, 2*n) tr[i]={0, MAXH};
  forn(i, k){
    pii interval = op[i]==1? make_pair(height[i], n) : make_pair(0, height[i]+1);
    modify(left[i], right[i]+1, interval);
  }
  for(int i=1; i<n; ++i){
    apply(i<<1, tr[i]);
    apply(i<<1|1, tr[i]);
  }
  forn(i, n) finalHeight[i]=tr[n+i].F;
  return;
}

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