Submission #1075238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075238		Boas	Wall (IOI14_wall)	C++17	100 / 100	2029 ms	102400 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

struct val
{
  int minv = 0, maxv = 100'000;
  val operator+(const val &b)
  {
    val a = *this, res;
    res.minv = max(a.minv, b.minv);
    res.maxv = min(a.maxv, b.maxv);
    if (b.minv > maxv)
      res.maxv = b.minv;
    if (b.maxv < minv)
      res.minv = b.maxv;
    return res;
  }
  val &operator+=(const val &b)
  {
    minv = max(minv, b.minv);
    maxv = min(maxv, b.maxv);
    if (b.minv > maxv)
      maxv = b.minv;
    if (b.maxv < minv)
      minv = b.maxv;
    return *this;
  }
};

vector<val> tree, lazy;
int treeN = 1;

void pull(int i)
{
  tree[i] = tree[2 * i] + tree[2 * i + 1];
}

void push(int i)
{
  tree[i] += lazy[i];
  if (i < treeN)
  {
    lazy[2 * i] += lazy[i];
    lazy[2 * i + 1] += lazy[i];
  }
  lazy[i] = {};
}

val query(int i, int l, int r, int ql, int qr, int v, int op)
{
  push(i);
  if (qr < l || r < ql)
    return {};
  if (ql <= l && r <= qr)
  {
    if (op == 1)
    {
      val add = {v, 100'000};
      lazy[i] += add;
      push(i);
    }
    else if (op == 2)
    {
      val add = {0, v};
      lazy[i] += add;
      push(i);
    }
    return tree[i];
  }
  int m = (l + r) / 2;
  val res = query(2 * i, l, m, ql, qr, v, op) +
            query(2 * i + 1, m + 1, r, ql, qr, v, op);
  pull(i);
  return res;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  while (treeN < n)
    treeN *= 2;
  tree = lazy = vector<val>(treeN * 2);
  for (int i = 0; i < k; i++)
  {
    int l = left[i], r = right[i], h = height[i];
    query(1, 0, treeN - 1, l, r, h, op[i]);
  }
  for (int i = 0; i < n; i++)
  {
    finalHeight[i] = query(1, 0, treeN - 1, i, i, 0, 0).minv;
  }
  return;
}

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