제출 #471436

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
471436		ashen_witch	벽 (IOI14_wall)	C++17	100 / 100	1438 ms	85956 KiB

wall

#include "bits/stdc++.h"
#include "wall.h"
 
using namespace std;
 
template <class T, class U, int SIZE>
struct LazySegTree {

  static_assert(__builtin_popcount(SIZE) == 1);

  const T kOpId = 0;
  const U kLazyId_1 = -1, kLazyId_2 = 1 << 17;

  T Op(T a, T b) {
    return max(a, b);
  }

  T tree[2 * SIZE];
  U lazy_1[2 * SIZE], lazy_2[2 * SIZE];

  LazySegTree() {
    for (int i = 0; i < 2 * SIZE; ++i)
      tree[i] = kOpId, lazy_1[i] = kLazyId_1, lazy_2[i] = kLazyId_2;
  }

  void Push(int cur, int low, int high) {
    int mid = (low + high) / 2;
    if (lazy_1[cur] != kLazyId_1) {
      Max(low, high, lazy_1[cur], 2 * cur, low, mid),
      Max(low, high, lazy_1[cur], 2 * cur + 1, mid + 1, high);
      lazy_1[cur] = kLazyId_1;
    }
    if (lazy_2[cur] != kLazyId_2) {
      Min(low, high, lazy_2[cur], 2 * cur, low, mid),
      Min(low, high, lazy_2[cur], 2 * cur + 1, mid + 1, high);
      lazy_2[cur] = kLazyId_2;
    }
  }

  void Pull(int cur) {
    tree[cur] = Op(tree[2 * cur], tree[2 * cur + 1]);
  }

  void Max(int l, int r, U val, int cur = 1, int low = 0, int high = SIZE - 1) {
    if (r < low || high < l)
      return;
    if (l <= low && high <= r) {
      tree[cur] = max(tree[cur], val);
      if (val > lazy_2[cur])
        lazy_1[cur] = lazy_2[cur] = val;
      else
        lazy_1[cur] = max(lazy_1[cur], val);
      return;
    }
    Push(cur, low, high);
    int mid = (low + high) / 2;
    Max(l, r, val, 2 * cur, low, mid),
    Max(l, r, val, 2 * cur + 1, mid + 1, high);
    Pull(cur);
  }

  void Min(int l, int r, U val, int cur = 1, int low = 0, int high = SIZE - 1) {
    if (r < low || high < l)
      return;
    if (l <= low && high <= r) {
      tree[cur] = min(tree[cur], val);
      lazy_2[cur] = min(lazy_2[cur], val);
      return;
    }
    Push(cur, low, high);
    int mid = (low + high) / 2;
    Min(l, r, val, 2 * cur, low, mid),
        Min(l, r, val, 2 * cur + 1, mid + 1, high);
    Pull(cur);
  }

  T Qry(int l, int r, int cur = 1, int low = 0, int high = SIZE - 1) {
    if (r < low || high < l)
      return kOpId;
    if (l <= low && high <= r)
      return tree[cur];
    Push(cur, low, high);
    int mid = (low + high) / 2;
    return Op(
        Qry(l, r, 2 * cur, low, mid),
        Qry(l, r, 2 * cur + 1, mid + 1, high)
    );
  }

};
 
const int kSize = 1 << 21;
 
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  LazySegTree<int, int, kSize> tree;
  for (int i = 0; i < k; ++i) {
    if (op[i] == 1)
      tree.Max(left[i], right[i], height[i]);
    else
      tree.Min(left[i], right[i], height[i]);
  }
  for (int i = 0; i < n; ++i)
    finalHeight[i] = tree.Qry(i, i);
}

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