Submission #117445

#	Time	Username	Problem	Language	Result	Execution time	Memory
117445		dragonslayerit	Wall (IOI14_wall)	C++14	100 / 100	728 ms	111224 KiB

wall

#include "wall.h"
#include <climits>
#include <algorithm>
#include <cassert>
#include <vector>

//clamps to [a,b]
struct Node{
  int a,b;
  Node():a(INT_MIN),b(INT_MAX){
  }
  Node(int a,int b):a(a),b(b){
    assert(a<=b);
  }
  int eval(int x){
    return std::max(a,std::min(b,x));
  }
};

//apply l, then r
struct Node combine(struct Node l,struct Node r){
  if(l.b<r.a) return Node(r.a,r.a);
  if(l.a>r.b) return Node(r.b,r.b);
  return Node(std::max(l.a,r.a),std::min(l.b,r.b));
}

struct Node st[1000005];
struct Node alt[500005];
std::vector<int> delta[2000005];
int K;

void pull(int i){
  st[i]=combine(st[i<<1],st[i<<1|1]);
}

void update(int i){
  for(i+=K;i>1;i>>=1){
    pull(i>>1);
  }
}

struct Node query(int a,int b){
  struct Node lsum,rsum;
  for(a+=K,b+=K;a<b;a>>=1,b>>=1){
    if(a&1) lsum=combine(lsum,st[a++]);
    if(b&1) rsum=combine(st[--b],rsum);
  }
  return combine(lsum,rsum);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  K=k;
  for(int i=0;i<k;i++){
    if(op[i]==1){
      alt[i]=Node(height[i],INT_MAX);
    }else{
      alt[i]=Node(INT_MIN,height[i]);
    }
    delta[left[i]].push_back(i);
    delta[right[i]+1].push_back(i);
  }
  for(int i=0;i<n;i++){
    for(int x:delta[i]){
      std::swap(st[x+K],alt[x]);
      update(x);
    }
    finalHeight[i]=query(0,K).eval(0);
  }
  return;
}

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