Submission #39646

#	Time	Username	Problem	Language	Result	Execution time	Memory
39646		funcsr	Wall (IOI14_wall)	C++14	100 / 100	846 ms	143092 KiB

wall

#include "wall.h"
#include <vector>
#include <iostream>
#include <set>
#include <queue>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define MAX_N (1<<19)
#define INF 1145141919
#define pb push_back

struct Node {
  int a, b;
  Node(int a, int b) : a(a), b(b) {}
  Node() : a(INF), b(0) {}
  int f(int x) { return min(a, max(b, x)); }
};

inline Node op(const Node &l, const Node &r) {
  return Node(min(r.a, max(l.a, r.b)), max(l.b, r.b));
}
Node seg[MAX_N*2-1];
void update(int k, const Node &v) {
  k += MAX_N-1;
  seg[k] = v;
  while (k > 0) {
    k = (k-1)/2;
    seg[k] = op(seg[k*2+1], seg[k*2+2]);
  }
}

vector<int> GL[2000000], GR[2000000];
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]) {
  rep(i, K) GL[left[i]].pb(i);
  rep(i, K) GR[right[i]].pb(i);
  rep(i, N) {
    for (int x : GL[i]) {
      if (op[x] == 1) update(x, Node(INF, height[x]));
      else update(x, Node(height[x], 0));
    }
    finalHeight[i] = seg[0].f(0);
    for (int x : GR[i]) update(x, Node());
  }
}

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