Submission #1144247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1144247		limits	Wall (IOI14_wall)	C++20	100 / 100	597 ms	78704 KiB

wall

#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define f0r(i, k) for (int i = 0; i < (k); ++i)
#define fnr(i, n, k) for (int i = (n); i < (k); ++i)
#define r0f(i, k) for (int i = (k); i >= 0; --i)
#define rnf(i, n, k) for (int i = (n); i >= k; --i)
#define forl(i, l) for (auto i : l)
#define ctn(x) cout << x << '\n'
#define ctl(lst)                            \
  {                                         \
    for (auto &a : (lst)) cout << a << ' '; \
    cout << endl;                           \
  }
#define pb push_back
#define F first
#define S second
#define all(v) (v).begin(), (v).end()
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define sz(v) (v).size()
#define ckmin(a, b) ((a) > (b) ? a = b, 1 : 0)
#define ckmax(a, b) ((a) < (b) ? a = b, 1 : 0)
#define pmod(a, b, md) a = (a + b) % md

using namespace std;

template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using Adj = V<vi>;

struct Node {
  int mn = 0, mx = INT_MAX;
};

struct LazySegTree {
  int n;
  V<Node> t;

  void apply(int v, const Node &x) {
    t[v].mn = max(t[v].mn, x.mn);
    t[v].mx = max(t[v].mx, x.mn);
    t[v].mx = min(t[v].mx, x.mx);
    t[v].mn = min(t[v].mn, t[v].mx);
  }

  void push_down(int v) {
    apply(2 * v, t[v]);
    apply(2 * v + 1, t[v]);
    t[v] = Node();
  }

  void upd(int v, int l, int r, int ql, int qr, const Node &x) {
    if (r < ql || qr < l) return;
    if (ql <= l && r <= qr) {
      apply(v, x);
      return;
    }
    push_down(v);
    int m = (l + r) / 2;
    upd(2 * v, l, m, ql, qr, x);
    upd(2 * v + 1, m + 1, r, ql, qr, x);
  }

  Node query(int v, int l, int r, int idx) {
    if (l == r) return t[v];
    push_down(v);
    int m = (l + r) / 2;
    return idx <= m ? query(2 * v, l, m, idx) : query(2 * v + 1, m + 1, r, idx);
  }

  LazySegTree(int n) : n(n), t(4 * n) {}
  void upd(int ql, int qr, const Node &x) { return upd(1, 0, n - 1, ql, qr, x); }
  Node get(int idx) { return query(1, 0, n - 1, idx); }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  LazySegTree st(n);
  f0r(i, k) {
    if (op[i] == 1) st.upd(left[i], right[i], {height[i], INT_MAX});
    else st.upd(left[i], right[i], {0, height[i]});
  }
  f0r(i, n) finalHeight[i] = st.get(i).mn;
}

#ifdef LOCAL
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  const int k = 6;
  int op[k] = {1, 2, 2, 1, 1, 2};
  int left[k] = {1, 4, 3, 0, 2, 6};
  int right[k] = {8, 9, 6, 5, 2, 7};
  int height[k] = {4, 1, 5, 3, 5, 0};
  int finalHeight[10];
  buildWall(10, k, op, left, right, height, finalHeight);
  f0r(i, 10) ctn(finalHeight[i]);
}
#endif

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