Submission #502155

#	Time	Username	Problem	Language	Result	Execution time	Memory
502155		benk	Growing Trees (BOI11_grow)	C++17	0 / 100	1097 ms	6836 KiB

grow

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

template <typename T>
using ordered_set = tree<T, null_type,
      less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;


struct node {
	ll ans = 0;
	int lazy = 0;
	bool islazy = false;
	// only used to assign value to 'leaf' nodes in build and pupd
	void assign(int val) {
		ans = val;
	}
	// used in build, rquery, pupd, rupd
	void merge(const node & l, const node & r) {
		ans = l.ans + r.ans;
	}
};

struct SegTree {
	int32_t len = 0;
	node zero;
	vector<node> tree;

	SegTree (int32_t _len = N) {
		len = _len;
		tree.resize((len << 2) + 10);
	}

	// if a node has lazy tag then its info is correct but its children's info
	// is old, so pushdown() before going into children
	inline void pushdown(int32_t v, int32_t cl, int32_t cr) {
		if (!tree[v].islazy) return;

		int32_t mid = (cl + cr) >> 1;
		apply((v << 1), cl, mid, tree[v].lazy);
		apply(((v << 1) | 1), mid + 1, cr, tree[v].lazy);

		tree[v].lazy = zero.lazy;
		tree[v].islazy = false;
		return;
	}
	// apply() is an auxillary function to apply range update and set lazy tag
	inline void apply(int32_t v, int32_t cl, int32_t cr, int val) {
		if (cl != cr) {
			tree[v].lazy += val;				// modify the lazy by val, eg. lazy += val
			tree[v].islazy = true;
		}
		// incorporate the change (=val) in node
		tree[v].ans += 1LL * (cr - cl + 1) * val;
		return;
	}
	void build(vector<int32_t> &a, int32_t v, int32_t cl, int32_t cr) {
		if (cl == cr) {
			tree[v].assign(a[cl]);
			return;
		}
		int32_t mid = (cl + cr) >> 1;
		build(a, (v << 1), cl, mid);
		build(a, ((v << 1) | 1), mid + 1, cr);
		tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
		return;
	}
	void build(vector<int32_t> &a) {
		build(a, 1, 0, len - 1);
		return;
	}
	node pquery(int32_t v, int32_t cl, int32_t cr, int32_t pos) {
		if (cl == cr) return tree[v];
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		if (pos <= mid) return pquery((v << 1), cl, mid, pos);
		return pquery(((v << 1) | 1), mid + 1, cr, pos);
	}
	node pquery(int32_t pos) {
		return pquery(1, 0, len - 1, pos);
	}
	node rquery(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r) {
		if (l > cr || r < cl) return zero;
		if (l <= cl && cr <= r) return tree[v];
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		node a, b, ans;
		a = rquery((v << 1), cl, mid, l, r);
		b = rquery(((v << 1) | 1), mid + 1, cr, l, r);
		ans.merge(a, b);
		return ans;
	}
	node rquery(int32_t l, int32_t r) {
		return rquery(1, 0, len - 1, l, r);
	}
	void pupd(int32_t v, int32_t cl, int32_t cr, int32_t pos, int val) {
		if (cl == cr) {
			tree[v].assign(val);
			return;
		}
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		if (pos <= mid) {
			pupd((v << 1), cl, mid, pos, val);
		} else {
			pupd(((v << 1) | 1), mid + 1, cr, pos, val);
		}
		tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
		return;
	}
	void pupd(int32_t pos, int val) {
		pupd(1, 0, len - 1, pos, val);
		return;
	}
	void rupd(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r, int val) {
		if (l > cr || r < cl) return;
		if (l <= cl && cr <= r) {
			apply(v, cl, cr, val);
			return;
		}
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		rupd((v << 1), cl, mid, l, r, val);
		rupd(((v << 1) | 1), mid + 1, cr, l, r, val);
		tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
		return;
	}
	void rupd(int32_t l, int32_t r, int val) {
		rupd(1, 0, len - 1, l, r, val);
	}

	int right_descend(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r, ll val) {
		if (cl > r || cr < l) return -1;
		if (l <= cl && cr <= r) {
			if (tree[v].ans < val) return -1;
		}
		if (cl == cr) return cl;
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		int res = right_descend((v << 1), cl, mid, l, r, val);
		if (res != -1) return res;
		return right_descend(((v << 1) | 1), mid + 1, cr, l, r, val);
	}
	int right_descend(int l, int r, ll val) {
		return right_descend(1, 0, len - 1, l, r, val);
	}
};

void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	sort(all(v));
	SegTree st(n);
	st.build(v);

	while (m--) {
		char ch;
		cin >> ch;
		if (ch == 'F') {
			int cap, h;
			cin >> cap >> h;
			int id1 = st.right_descend(0, n - 1, h);
			if (id1 == - 1) continue;
			if (id1 + cap >= n) st.rupd(id1, n - 1, 1);
			else {
				ll curr = st.pquery(id1 + cap).ans;
				int id2 = st.right_descend(0, n - 1, curr);
				st.rupd(id1, id2 - 1, 1);
				int id3 = st.right_descend(0, n - 1, curr + 1);
				if (id3 == -1) id3 = n;
				id3--;
				int left = cap - (id2 - id1);
				st.rupd(id3 - left + 1, id3, 1);
			}
		} else {
			int mn, mx;
			cin >> mn >> mx;
			int id1 = st.right_descend(0, n - 1, mn);
			int id2 = st.right_descend(0, n - 1, mx + 1);
			if (id1 == -1) cout << "0\n";
			else if (id2 == -1) cout << n - id1 << '\n';
			else cout << id2 - id1 <<  '\n';
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
		cout << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10