Submission #1148068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148068		0x34c	Wall (IOI14_wall)	C++20	100 / 100	837 ms	79684 KiB

wall

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

const int INF = 1e9;

struct segtree
{
private:
  int n;
  vector<int> mntree, mxtree;
  vector<bool> lazy;

  void comb(int v)
  {
    mntree[v] = min(mntree[2 * v], mntree[2 * v + 1]);
    mxtree[v] = max(mxtree[2 * v], mxtree[2 * v + 1]);
  }

  void do_lazy(int v, int tl, int tr)
  {
    if (!lazy[v])
      return;

    if (tl != tr)
    {
      mntree[2 * v] = max(mntree[2 * v], mntree[v]);
      mxtree[2 * v] = max(mxtree[2 * v], mntree[2 * v]);
      mxtree[2 * v] = min(mxtree[2 * v], mxtree[v]);
      mntree[2 * v] = min(mntree[2 * v], mxtree[2 * v]);
      lazy[2 * v] = true;

      mntree[2 * v + 1] = max(mntree[2 * v + 1], mntree[v]);
      mxtree[2 * v + 1] = max(mxtree[2 * v + 1], mntree[2 * v + 1]);
      mxtree[2 * v + 1] = min(mxtree[2 * v + 1], mxtree[v]);
      mntree[2 * v + 1] = min(mntree[2 * v + 1], mxtree[2 * v + 1]);
      lazy[2 * v + 1] = true;
    }
    lazy[v] = false;
  }

  void update_min(int l, int r, int h, int v, int tl, int tr)
  {
    do_lazy(v, tl, tr);
    if (tr < l || r < tl)
      return;
    if (l <= tl && tr <= r)
    {
      mxtree[v] = min(mxtree[v], h);
      mntree[v] = min(mntree[v], mxtree[v]);
      lazy[v] = true;
      return;
    }

    int m = (tl + tr) / 2;
    update_min(l, r, h, 2 * v, tl, m);
    update_min(l, r, h, 2 * v + 1, m + 1, tr);
    comb(v);
  }

  void update_max(int l, int r, int h, int v, int tl, int tr)
  {
    do_lazy(v, tl, tr);
    if (tr < l || r < tl)
      return;
    if (l <= tl && tr <= r)
    {
      mntree[v] = max(mntree[v], h);
      mxtree[v] = max(mxtree[v], mntree[v]);
      lazy[v] = true;
      return;
    }

    int m = (tl + tr) / 2;
    update_max(l, r, h, 2 * v, tl, m);
    update_max(l, r, h, 2 * v + 1, m + 1, tr);
    comb(v);
  }

  int query(int idx, int v, int tl, int tr)
  {
    do_lazy(v, tl, tr);
    if (tl == tr)
      return mntree[v];
    else
    {
      int m = (tl + tr) / 2;
      if (idx <= m)
        return query(idx, 2 * v, tl, m);
      else
        return query(idx, 2 * v + 1, m + 1, tr);
    }
  }

public:
  segtree(int _n)
  {
    n = _n;
    mntree.resize(4 * n, 0);
    mxtree.resize(4 * n, 0);
    lazy.resize(4 * n, false);
  }

  void update_max(int l, int r, int h)
  {
    if (l > r)
      swap(l, r);
    update_max(l, r, h, 1, 0, n - 1);
  }

  void update_min(int l, int r, int h)
  {
    if (l > r)
      swap(l, r);
    update_min(l, r, h, 1, 0, n - 1);
  }

  int query(int idx)
  {
    return query(idx, 1, 0, n - 1);
  }
};

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

  for (int i = 0; i < k; i++)
  {
    if (op[i] == 1)
      tree.update_max(left[i], right[i], height[i]);
    else
      tree.update_min(left[i], right[i], height[i]);

    // for (int i = 0; i < n; i++)
    //   cout << tree.query(i) << ' ';
    // cout << endl;
  }

  for (int i = 0; i < n; i++)
    finalHeight[i] = tree.query(i);

  return;
}

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