Submission #680386

#	Time	Username	Problem	Language	Result	Execution time	Memory
680386		MattTheNub	Wall (IOI14_wall)	C++17	8 / 100	3069 ms	15220 KiB

wall

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

using namespace std;
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';

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

struct Node {
  int dec, inc;

  // dec = 0
  // inc = 9
  // -> dec=9, inc=9
  //
  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
// dec>=inc holds
// order matters

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

  int n;
  v<T> seg;
  void init(int _n) {
    n = _n;
    seg.assign(2 * n, ID);
  }
  void push(int p) {
    if (seg[p].dec != INT_MAX) {
      dbg(p);
      dbg(seg[p].dec);
      seg[2 * p].cdec(seg[p].dec);
      seg[2 * p + 1].cdec(seg[p].dec);
      seg[p].dec = INT_MAX;
    }
    if (seg[p].inc != -1) {
      dbg(p);
      dbg(seg[p].inc);
      seg[2 * p].cinc(seg[p].inc);
      seg[2 * p + 1].cinc(seg[p].inc);
      seg[p].inc = -1;
    }
  }
  // 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) { inc(1, 0, n - 1, l, r, val); }
  void inc(int p, int l, int r, int a, int b, int v) {
    if (a > r || b < l)
      return;
    if (a <= l && r <= b) {
      seg[p].cinc(v);
      return;
    }
    int mid = (l + r) / 2;
    push(p);
    inc(2 * p, l, mid, a, b, v);
    inc(2 * p + 1, mid + 1, r, a, b, v);
    // pull(p);
  }

  void dec(int l, int r, int val) { dec(1, 0, n - 1, l, r, val); }
  void dec(int p, int l, int r, int a, int b, int v) {
    if (a > r || b < l)
      return;
    if (p == 10) {
      dbg(l);
      dbg(r);
      dbg(a);
      dbg(b);
      dbg(v);
    }
    if (a <= l && r <= b) {
      seg[p].cdec(v);
      return;
    }
    int mid = (l + r) / 2;
    push(p);
    dec(2 * p, l, mid, a, b, v);
    dec(2 * p + 1, mid + 1, r, a, b, v);
    // pull(p);
  }

  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(1 << (int)ceil(log2(n)));
  for (int i = 0; i < n; i++) {
    w.upd(i, {0, 0});
  }
  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]);
    }
    // cerr << w.get(3).inc << '\n';
  }

  for (int i = 1; i < w.n; i++) {
    w.push(i);
    // cerr << w.seg[0].inc << ';';
  }

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

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