oj.uz

Submission #502190

# Submission time Handle Problem Language Result Execution time Memory
502190 2022-01-05T12:45:56 Z benk Growing Trees (BOI11_grow) C++17
0 / 100
 1000 ms 6840 KB 
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
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);
				if (id1 != id2) 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();
	}
	return 0;
}

Compilation message

grow.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
grow.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 6148 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 332 KB Output is correct
2 Correct 48 ms 444 KB Output is correct
3 Correct 30 ms 432 KB Output is correct
4 Correct 26 ms 432 KB Output is correct
5 Execution timed out 1095 ms 796 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 792 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 1092 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 4628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 5280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 5636 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 6036 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 5964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 6840 KB Time limit exceeded