Submission #899910

#	Time	Username	Problem	Language	Result	Execution time	Memory
899910		TAhmed33	Fish 2 (JOI22_fish2)	C++98	25 / 100	4065 ms	11044 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))
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
const int MAXN = 1e5 + 25;
typedef long long ll;
ll a[MAXN], pref[MAXN];
int sparse[17][MAXN];
inline int query (int l, int r) {
	int m = __lg(r - l + 1);
	int x = sparse[m][l], y = sparse[m][r - (1 << m) + 1];
	if (a[x] > a[y]) return x;
	return y;
}
inline ll get (int l, int r) {
	return pref[r] - pref[l - 1];
}
int n;
void build () {
	for (int i = 1; i <= n; i++) {
		pref[i] = a[i] + pref[i - 1];
		sparse[0][i] = i;
	}
	for (int i = 1; i < 17; i++) {
		for (int j = 1; j + (1 << i) - 1 <= n; j++) {
			int x = sparse[i - 1][j], y = sparse[i - 1][j + (1 << (i - 1))];
			if (a[x] > a[y]) sparse[i][j] = x;
			else sparse[i][j] = y;
		}
	}
}
int ans (int l, int r) {
	if (l == r) return 1;
	auto u = query(l, r);
	int ret = 1;
	if (u - 1 >= l && get(l, u - 1) >= a[u]) ret += ans(l, u - 1);
	if (u + 1 <= r && get(u + 1, r) >= a[u]) ret += ans(u + 1, r);
	return ret; 
}
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int q;
	cin >> q;
	int last = 0;
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int x, y;
			cin >> x >> y;
			a[x] = y;
			last = 0;
		} else {
			int l, r;
			cin >> l >> r;
			if (last == 0) {
				last = 1;
				build();
			}
			cout << ans(l, r) << '\n';
		}
	}
}

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