Submission #1214542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214542		bbldrizzy	Wall (IOI14_wall)	C++20	61 / 100	882 ms	282380 KiB

wall

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

struct Query {
  ll mn = 0;
  ll mx = 1e9;
};

template <typename T> class LazySegtree {
  private:
	const int sz;
	vector<Query> tree;      // tree[i] = sum of this node's range
	vector<Query> lazy;  // lazy[i] = lazy update for the range

	/** builds the segtree nodes */
	void build(int v, int l, int r, const vector<T> &a) {
		if (l == r) {
			tree[v].mn = a[l];
			tree[v].mx = a[l];
		} else {
			int m = (l + r) / 2;
			build(2 * v, l, m, a);
			build(2 * v + 1, m + 1, r, a);
			tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
			tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
		}
	}

	/** applies lazy update to tree[v], places update at lazy[v] */
	void apply(int v, int len, const Query &x) {
    ll maxz = x.mx;
    ll minz = x.mn;
    ll maxv = lazy[v].mx;
    ll minv = lazy[v].mn;
    if (maxz < tree[v].mn) {
      tree[v].mx = maxz;
      tree[v].mn = maxz;
    } else if (minz > tree[v].mx) {
      tree[v].mx = minz;
      tree[v].mn = minz;
    } else {
      tree[v].mx = min(maxz, tree[v].mx);
      tree[v].mn = max(minz, tree[v].mn);
    }
    if (maxz < minv) {
      lazy[v].mx = maxz;
      lazy[v].mn = maxz;
    } else if (minz > maxv) {
      lazy[v].mx = minz;
      lazy[v].mn = minz;
    } else {
      lazy[v].mx = min(maxz, maxv);
      lazy[v].mn = max(minz, minv);
    }
	}

	/** pushes down lazy update to children of v */
	void push_down(int v, int l, int r) {
		int m = (l + r) / 2;
		apply(2 * v, m - l + 1, lazy[v]);
		apply(2 * v + 1, r - m, lazy[v]);
		lazy[v] = Query();
	}

	void range_update(int v, int l, int r, int ql, int qr, const Query &x) {
		if (qr < l || ql > r) { return; }
		if (ql <= l && r <= qr) {
			apply(v, r - l + 1, x);
		} else {
			push_down(v, l, r);
			int m = (l + r) / 2;
			range_update(2 * v, l, m, ql, qr, x);
			range_update(2 * v + 1, m + 1, r, ql, qr, x);
			tree[v].mn = min(tree[2*v].mn, tree[2*v+1].mn);
			tree[v].mx = max(tree[2*v].mx, tree[2*v+1].mx);
		}
	}

	T query(int v, int l, int r, int ql) {
		if (l == r) { 
      return tree[v].mn; 
    } else {
      push_down(v, l, r);
      int m = (l + r) / 2;
      if (ql <= m) {
        return query(2 * v, l, m, ql);
      } else {
        return query(2 * v + 1, m+1, r, ql);
      }
    }
	}

  public:
	LazySegtree(const vector<T> &a) : sz(a.size()), tree(4 * sz), lazy(4 * sz) {
		build(1, 0, sz - 1, a);
	}

	/** updates [ql, qr] with the update x */
	void range_update(int ql, int qr, const Query &x) {
		range_update(1, 0, sz - 1, ql, qr, x);
	}

	/** sum of array values on [ql, qr] */
	T query(int ql) { return query(1, 0, sz - 1, ql); }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int final_height[]) {
  vector<ll> a(n, 0);
  LazySegtree<ll> st(a);
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) {
      st.range_update(left[i], right[i], Query{height[i], (ll)1e9});
    } else {
      st.range_update(left[i], right[i], {0, height[i]});
    }
  }
  for (int i = 0; i < n; i++) {
    // cout << "st.query(i): " << st.query(i) << "\n";
    final_height[i] = st.query(i);
  }
}

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