Submission #671056

#	Time	Username	Problem	Language	Result	Execution time	Memory
671056		ThinGarfield	Wall (IOI14_wall)	C++11	100 / 100	802 ms	84032 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

#define F first
#define S second
#define lc 2 * p
#define rc 2 * p + 1

constexpr int logn = 21;
constexpr int maxn = (1 << logn);
constexpr ll infty = LLONG_MAX;

pll seg[maxn * 2];

// t1 is old trim; t2 is new trim
pll combine(pll t1, pll t2) {
  if (t1.F > t2.S) return make_pair(t2.S, t2.S);
  if (t2.F > t1.S) return make_pair(t2.F, t2.F);
  return make_pair(max(t1.F, t2.F), min(t1.S, t2.S));
}

void pushdn(int p) {
  seg[lc] = combine(seg[lc], seg[p]);
  seg[rc] = combine(seg[rc], seg[p]);
  seg[p] = make_pair(0, infty);  // makes p irrelevant
}

void rangeupdate(int p, int l, int r, int a, int b, pll val) {
  if (a > r || b < l) return;
  if (a <= l && r <= b) {
    seg[p] = combine(seg[p], val);
    return;
  }
  pushdn(p);
  int mid = (l + r) / 2;
  rangeupdate(lc, l, mid, a, b, val);
  rangeupdate(rc, mid + 1, r, a, b, val);
}

pll walkseg(int p, int l, int r, int idx) {
  if (l == r) {
    assert(idx == l);
    return seg[p];
  }
  int mid = (l + r) / 2;
  if (idx <= mid) {
    return combine(walkseg(lc, l, mid, idx), seg[p]);
  } else {
    return combine(walkseg(rc, mid + 1, r, idx), seg[p]);
  }
}

ll compute(pll trim, ll val) {
  if (val < trim.F) return trim.F;
  if (val < trim.S) return trim.S;
  return val;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  // cout << n << ' ' << k << '\n';
  for (int i = 0; i < k; i++) {
    // cout << "query " << op[i] << ' ' << left[i] << ' ' << right[i] << ' ' << height[i] << '\n';
    if (op[i] == 1) {
      rangeupdate(1, 0, maxn - 1, left[i], right[i], make_pair(height[i], infty));
    } else {
      rangeupdate(1, 0, maxn - 1, left[i], right[i], make_pair(0, height[i]));
    }
  }
  for (int i = 0; i < n; i++) {
    finalHeight[i] = compute(walkseg(1, 0, maxn - 1, i), 0);
  }
  return;
}

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