Submission #1209707

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209707		tiongg	Wall (IOI14_wall)	C++20	0 / 100	157 ms	8012 KiB

wall

#include "wall.h"

#include "bits/stdc++.h"
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using ll = long long;
using ull = unsigned long long;
using pairll = std::pair<ll, ll>;
using pairi = std::pair<int, int>;

using namespace std;
#define forn(i, n) for (ll i = 0; i < (n); ++i)
#define fora(i, a, b) for (ll i = (a); i <= (b); ++i)
#define ford(i, a, b) for (ll i = (a); i >= (b); --i)

#define to_int(x) static_cast<int>((x))
#define to_long(x) static_cast<long>((x))
#define to_ll(x) static_cast<long long>((x))

#define all(v) (v).begin(), (v).end()
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define LSB(x) ((x) & -(x))
#define LSBPos(x) to_ll(log2(LSB(x)))
#define contains(container, x) ((container).find((x)) != (container).end())
#define CMP(name, type, body)                                                  \
  struct name {                                                                \
    bool operator()(const type &a, const type &b) const { return (body); }     \
  };

#define foreach(v, i) for (auto i = (v).begin(); i != (v).end(); ++i)
#define debug(x) std::cout << #x << " = " << (x) << std::endl
#define print_vec(v)                                                           \
  do {                                                                         \
    for (const auto &val : (v))                                                \
      std::cout << val << " ";                                                 \
    std::cout << std::endl;                                                    \
  } while (0);
#define print_pair(p)                                                          \
  std::cout << "(" << (p).first << ", " << (p).second << ")" << std::endl
#define print_mat(m)                                                           \
  for (const auto &vec : m)                                                    \
  print_vec(vec)

/* Custom printing statements */
void print(string s) { cout << s << endl; }

void print_set(set<ll> s) {
  for (auto it = s.begin(); it != s.end(); ++it)
    cout << *it << " ";
  cout << endl;
}

void print_map(map<ll, ll> m) {
  for (auto it = m.begin(); it != m.end(); ++it) {
    cout << it->first << "->" << it->second;
    cout << endl;
  }
  cout << endl;
}

template <typename T> void print_pq(T pq) {
  cout << "pq: ";
  while (!pq.empty()) {
    ll top = pq.top();
    pq.pop();
    cout << top << ", ";
  }
  cout << endl;
}

class LazySegmentTree {
public:
  int n;
  vector<ll> t;
  vector<ll> lazy_min, lazy_max;
  vector<bool> is_min_first;

  LazySegmentTree(int size)
      : n{size}, t{vector<ll>(4 * size, 0ll)},
        lazy_min{vector<ll>(4 * size, LLONG_MIN)},
        lazy_max{vector<ll>(4 * size, LLONG_MAX)},
        is_min_first{vector<bool>(4 * size, false)} {}

  void modify(int l, int r, ll v, bool is_min) {
    modify(l, r, v, is_min, 0, 0, n);
  }

  void modify(int l, int r, ll v, bool is_min, int x, int lx, int rx) {
    if (lx >= r || l >= rx) {
      return;
    }
    // Current range encompasses target range
    if (lx >= l && r >= rx) {
      if (is_min) {
        apply(v, LLONG_MAX, is_min, x, lx, rx);
      } else {
        apply(LLONG_MIN, v, is_min, x, lx, rx);
      }
      return;
    }

    // Target range is somewhere further down
    push(x, lx, rx);
    int mid = (lx + rx) / 2;
    modify(l, r, v, is_min, x * 2 + 1, lx, mid);
    modify(l, r, v, is_min, x * 2 + 2, mid, rx);

    t[x] = t[x * 2 + 1] + t[x * 2 + 2];
  }

  ll query(int l, int r) { return query(l, r, 0, 0, n); }

  ll query(int l, int r, int x, int lx, int rx) {
    if (lx >= r || l >= rx) {
      return 0;
    }
    if (lx >= l && rx <= r) {
      return t[x];
    }
    push(x, lx, rx);
    int mid = (lx + rx) / 2;
    ll left_res = query(l, r, x * 2 + 1, lx, mid);
    ll right_res = query(l, r, x * 2 + 2, mid, rx);
    return left_res + right_res;
  }

  void push(int x, int lx, int rx) {
    // Leaf node
    if (rx - lx == 1) {
      return;
    }
    int mid = (lx + rx) / 2;
    apply(lazy_min[x], lazy_max[x], is_min_first[x], x * 2 + 1, lx, mid);
    apply(lazy_min[x], lazy_max[x], is_min_first[x], x * 2 + 2, mid, rx);

    lazy_max[x] = LLONG_MAX;
    lazy_min[x] = LLONG_MIN;
    is_min_first[x] = false;
  }

  // Propogate val to x
  void apply(ll set_min, ll set_max, bool min_first, int x, int lx, int rx) {
    int affected_count = rx - lx;

    if (min_first) {
      t[x] = max(t[x], set_min);
      t[x] = min(t[x], set_max);
    } else {
      t[x] = min(t[x], set_max);
      t[x] = max(t[x], set_min);
    }

    lazy_min[x] = max(lazy_min[x], set_min);
    lazy_max[x] = min(lazy_max[x], set_max);
    is_min_first[x] = min_first;
  }
};

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

  LazySegmentTree t(n);

  for (int i = 0; i < k; i++) {
    int type = op[i];
    int l = left[i];
    int r = right[i];
    int x = height[i];
    r++;

    // Add
    // Min height = x
    if (type == 1) {
      t.modify(l, r, x, true);
    }

    // Remove
    // Max height = x
    if (type == 2) {
      t.modify(l, r, x, false);
    }
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = t.query(i, i + 1);
  }
}

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