Submission #899903

#	Time	Username	Problem	Language	Result	Execution time	Memory
899903		TAhmed33	Fish 2 (JOI22_fish2)	C++98	13 / 100	4081 ms	4956 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
#define mid ((l + r) >> 1)
#define tl (node + 1)
#define tr (node + 2 * (mid - l + 1))
const int MAXN = 1e5 + 25;
typedef long long ll;
struct SegmentTree {
	int a[MAXN]; ll sum[MAXN << 1];
	pair <int, int> mx[MAXN << 1];
	void build (int l, int r, int node) {
		if (l == r) {
			sum[node] = a[l];
			mx[node] = {a[l], l};
		} else {
			build(l, mid, tl);
			build(mid + 1, r, tr);
			mx[node] = max(mx[tl], mx[tr]);
			sum[node] = sum[tl] + sum[tr];
		}
	}
	void update (int l, int r, int a2, int b, int node) {
		if (l == r) {
			sum[node] = b; a[l] = b;
			mx[node] = {b, l};
			return;
		}
		if (a2 <= mid) update(l, mid, a2, b, tl);
		else update(mid + 1, r, a2, b, tr);
		mx[node] = max(mx[tl], mx[tr]);
		sum[node] = sum[tl] + sum[tr];
	}
	ll get_sum (int l, int r, int a, int b, int node) {
		if (l >= a && r <= b) return sum[node];
		if (l > b || r < a) return 0;
		return get_sum(l, mid, a, b, tl) + get_sum(mid + 1, r, a, b, tr);
	}
	pair <int, int> get_mx (int l, int r, int a, int b, int node) {
		if (l >= a && r <= b) return mx[node];
		if (l > b || r < a) return {0, 0};
		return max(get_mx(l, mid, a, b, tl), get_mx(mid + 1, r, a, b, tr));
	}
} cur;
int n;
int ans (int l, int r) {
	if (l == r) return 1;
	auto u = cur.get_mx(1, n, l, r, 1);
	int ret = 1;
	if (u.second - 1 >= l && cur.get_sum(1, n, l, u.second - 1, 1) >= cur.a[u.second]) ret += ans(l, u.second - 1);
	if (u.second + 1 <= r && cur.get_sum(1, n, u.second + 1, r, 1) >= cur.a[u.second]) ret += ans(u.second + 1, r);
	return ret; 
}
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> cur.a[i];
	cur.build(1, n, 1);
	int q;
	cin >> q;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int x, y;
			cin >> x >> y;
			cur.update(1, n, x, y, 1);
		} else {
			int l, r;
			cin >> l >> r;
			cout << ans(l, r) << '\n';
		}
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17