Submission #561639

#	Time	Username	Problem	Language	Result	Execution time	Memory
561639		DanShaders	Fish 2 (JOI22_fish2)	C++17	25 / 100	4070 ms	3668 KiB

fish2

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;

namespace x = __gnu_pbds;
template <typename T>
using ordered_set = x::tree<T, x::null_type, less<T>, x::rb_tree_tag, x::tree_order_statistics_node_update>;

template <typename T>
using normal_queue = priority_queue<T, vector<T>, greater<>>;

#define all(x) begin(x), end(x)
#define sz(x) ((int) (x).size())
#define x first
#define y second
using ll = long long;
using ld = long double;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int left_[N], right_[N];
ll pref[N];
pair<int, int> go[N];
int balance[N];

int get(int *a, int n) {
	for (int i = 0; i < n; ++i) {
		pref[i + 1] = pref[i] + a[i];
	}
	for (int i = 0; i < n; ++i) {
		left_[i] = i - 1;
		while (left_[i] >= 0 && pair{a[left_[i]], left_[i]} < pair{a[i], i}) {
			left_[i] = left_[left_[i]];
		}
	}
	for (int i = n; i--; ) {
		right_[i] = i + 1;
		while (right_[i] < n && pair{a[right_[i]], right_[i]} < pair{a[i], i}) {
			right_[i] = right_[right_[i]];
		}
	}
	fill(balance, balance + n + 1, 0);
	
	auto ai = [&](int i) {
		if (i < 0 || i >= n) {
			return +INF;
		}
		return a[i];
	};

	for (int i = 0; i < n; ++i) {
		int lef = left_[i], rig = right_[i];
		if (pref[rig] - pref[lef + 1] < min(ai(lef), ai(rig)) && (lef != -1 || rig != n)) {
			++balance[lef + 1];
			--balance[rig];
		}
	}
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		balance[i + 1] += balance[i];
		if (!balance[i]) {
			++ans;
		}
	}
	return ans;
}

int a[N];

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	int queries;
	cin >> queries;
	while (queries--) {
		int type, l, r;
		cin >> type >> l >> r;
		if (type == 1) {
			a[l - 1] = r;
		} else {
			cout << get(a + l - 1, r - l + 1) << "\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