Submission #561654

#	Time	Username	Problem	Language	Result	Execution time	Memory
561654		DanShaders	Fish 2 (JOI22_fish2)	C++17	0 / 100	1 ms	340 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 = 512, INF = 0x3f3f3f3f;

pair<int, int> t[2 * N];
int mod[2 * N];

pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
	if (a.x == b.x) {
		return {a.x, a.y + b.y};
	}
	return min(a, b);
}

void tapply(int i, int x) {
	mod[i] += x;
	t[i].x += x;
}

void tpush(int i) {
	if (mod[i]) {
		tapply(2 * i + 1, mod[i]);
		tapply(2 * i + 2, mod[i]);
		mod[i] = 0;
	}
}

void tpull(int i) {
	t[i] = merge(t[2 * i + 1], t[2 * i + 2]);
}

void tadd(int ql, int qr, int x, int ci = 0, int cl = 0, int cr = N) {
	if (ql <= cl && cr <= qr) {
		tapply(ci, x);
		return;
	}
	if (qr <= cl || cr <= ql) {
		return;
	}
	int mid = (cl + cr) / 2;
	tpush(ci);
	tadd(ql, qr, x, 2 * ci + 1, cl, mid);
	tadd(ql, qr, x, 2 * ci + 2, mid, cr);
	tpull(ci);
}

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) {
		t[N - 1 + i] = {0, 1};
	}
	for (int i = N - 1; i--; ) {
		t[i] = merge(t[2 * i + 1], t[2 * i + 2]);
	}

	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)) {
			tadd(lef + 1, rig + 1, 1);
		}
	}
	return t[0].y;
}

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: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17