Submission #680036

#	Time	Username	Problem	Language	Result	Execution time	Memory
680036		MattTheNub	Wall (IOI14_wall)	C++17	0 / 100	140 ms	14044 KiB

wall

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

using namespace std;

template <class T> using v = vector<T>;

struct Node {
  int dec, inc;

  void cinc(int val) {
    if (dec < val) {
      dec = val;
    }
    inc = max(inc, val);
  }
  void cdec(int val) {
    if (inc > val) {
      inc = val;
    }
    dec = min(dec, val);
  }
};

// h=0, increase to 2, decrease to 1 -> 1
// h=0, decrease to 1, increase to 2 -> 2
// order matters

template <class T> struct Seg {
  // TODO: implement
  const T ID = {0, 0}; // comb(ID,b) = b
  T comb(T a, T b) {}

  int n;
  v<T> seg;
  void init(int _n) {
    n = _n;
    seg.assign(2 * n, ID);
  }
  void push(int p) {}
  // void pull(int p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }
  // void upd(int p, T val) { // set val at position p
  //   seg[p += n] = val;
  //   for (p /= 2; p; p /= 2)
  //     pull(p);
  // }
  void inc(int l, int r, int val) {
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1)
        seg[l++].cinc(val);
      if (r & 1)
        seg[--r].cinc(val);
    }
  }
  void dec(int l, int r, int val) {
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1)
        seg[l++].cdec(val);
      if (r & 1)
        seg[--r].cdec(val);
    }
  }
  T get(int p) { return seg[p + n]; }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {

  Seg<Node> w;
  w.init(n);
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) {
      w.inc(left[i], right[i], height[i]);
    } else {
      w.dec(left[i], right[i], height[i]);
    }
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = w.get(i).inc;
  }
}

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