Submission #1148035

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148035		0x34c	Wall (IOI14_wall)	C++20	0 / 100	216 ms	8008 KiB

wall

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

int UPDATE_ID = 0;
const int INF = 1e9;

struct segtree
{
private:
  int n;
  vector<int> mntree, mxtree, mnlazy, mxlazy, mnid, mxid;
  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 (mnid[v] > mxid[v])
    {
      if (mxid[v] != -1)
      {
        mxtree[v] = min(mxtree[v], mxlazy[v]);
        mntree[v] = min(mntree[v], mxtree[v]);
      }

      if (mnid[v] != -1)
      {
        mntree[v] = max(mntree[v], mnlazy[v]);
        mxtree[v] = max(mxtree[v], mntree[v]);
      }
    }
    else
    {
      if (mnid[v] != -1)
      {
        mntree[v] = max(mntree[v], mnlazy[v]);
        mxtree[v] = max(mxtree[v], mntree[v]);
      }

      if (mxid[v] != -1)
      {
        mxtree[v] = min(mxtree[v], mxlazy[v]);
        mntree[v] = min(mntree[v], mxtree[v]);
      }
    }

    if (tl != tr)
    {
      if (mxid[v] != -1)
      {
        mxid[2 * v] = mxid[v];
        mxid[2 * v + 1] = mxid[v];
        mxlazy[2 * v] = mxlazy[v];
        mxlazy[2 * v + 1] = mxlazy[v];
        lazy[2 * v] = true;
        lazy[2 * v + 1] = true;
      }

      if (mnid[v] != -1)
      {
        mnid[2 * v] = mnid[v];
        mnid[2 * v + 1] = mnid[v];
        mnlazy[2 * v] = mnlazy[v];
        mnlazy[2 * v + 1] = mnlazy[v];
        lazy[2 * v] = true;
        lazy[2 * v + 1] = true;
      }
    }

    mxid[v] = mnid[v] = -1;
    mnlazy[v] = -INF;
    mxlazy[v] = INF;
    lazy[v] = false;
  }

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

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

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

    int m = (tl + tr) / 2;
    update_max(l, r, h, id, 2 * v, tl, m);
    update_max(l, r, h, id, 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);
    mnlazy.resize(4 * n, -INF);
    mxlazy.resize(4 * n, INF);
    mnid.resize(4 * n, -1);
    mxid.resize(4 * n, -1);
    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, UPDATE_ID++, 1, 0, n - 1);
  }

  void update_min(int l, int r, int h)
  {
    if (l > r)
      swap(l, r);
    update_min(l, r, h, UPDATE_ID++, 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++)
    finalHeight[i] = tree.query(i);

  return;
}

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