Submission #561725

#	Time	Username	Problem	Language	Result	Execution time	Memory
561725		DanShaders	Fish 2 (JOI22_fish2)	C++17	25 / 100	4033 ms	16696 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 = 1 << 17, 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) {
	t[i].x += x;
	mod[i] += 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);
}
 
pair<int, int> tget(int ql, int qr, int ci = 0, int cl = 0, int cr = N) {
	if (ql <= cl && cr <= qr) {
		return t[ci];
	}
	if (qr <= cl || cr <= ql) {
		return {+INF, 0};
	}
	int mid = (cl + cr) / 2;
	tpush(ci);
	return merge(
		tget(ql, qr, 2 * ci + 1, cl, mid),
		tget(ql, qr, 2 * ci + 2, mid, cr)
	);
}
 
pair<int, int> g[2 * N];
ll gs[2 * N];
 
void gset(int i, int x) {
	i += N;
	g[i] = {x, i};
	gs[i] = x;
	i /= 2;
	while (i) {
		g[i] = max(g[2 * i], g[2 * i + 1]);
		gs[i] = gs[2 * i] + gs[2 * i + 1];
		i /= 2;
	}
}
 
pair<int, int> gget(int l, int r) {
	l += N, r += N - 1;
	pair<int, int> ans = {-1, -1};
	while (l <= r) {
		if (l & 1)	ans = max(ans, g[l]);
		if (!(r & 1))	ans = max(ans, g[r]);
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
 
ll gsum(int l, int r) {
	l += N, r += N - 1;
	ll ans = 0;
	while (l <= r) {
		if (l & 1)	ans += gs[l];
		if (!(r & 1))	ans += gs[r];
		l = (l + 1) / 2;
		r = (r - 1) / 2;
	}
	return ans;
}
 
int gfirstgreater(int ql, int qr, ll x, int ci = 1, int cl = 0, int cr = N) {
	if (qr <= cl || cr <= ql || g[ci].x <= x) {
		return qr;
	}
	if (cr - cl == 1) {
		return cl;
	}
	int mid = (cl + cr) / 2;
	int res = gfirstgreater(ql, qr, x, 2 * ci, cl, mid);
	if (res >= qr) {
		return gfirstgreater(ql, qr, x, 2 * ci + 1, mid, cr);
	} else {
		return res;
	}
}
 
int glastgreater(int ql, int qr, ll x, int ci = 1, int cl = 0, int cr = N) {
	if (qr <= cl || cr <= ql || g[ci].x <= x) {
		return ql - 1;
	}
	if (cr - cl == 1) {
		return cl;
	}
	int mid = (cl + cr) / 2;
	int res = glastgreater(ql, qr, x, 2 * ci + 1, mid, cr);
	if (res < ql) {
		return glastgreater(ql, qr, x, 2 * ci, cl, mid);
	} else {
		return res;
	}
}
 
int a[N], n;
int up[N], left_[N], right_[N];
 
void set_up_to(int i, int x) {
	if (up[i] != x) {
		up[i] = x;
		if (!x) {
			tadd(left_[i] + 1, right_[i], -1);
		} else {
			tadd(left_[i] + 1, right_[i], 1);
		}
	}
}
 
void loop_set_up(int u, int l, int r, int x, vector<pair<int, int>> &change) {
	assert(l <= u && u < r);
	auto ai = [&](int i) {
		if (i < l || i >= r) {
			return +INF;
		}
		return a[i];
	};
 
	int cl = max(left_[u], l - 1), cr = min(right_[u], r);
	ll sm = gsum(cl + 1, cr);
	// cout << "loop_set_up" << u << " " << l << " " << r << " " << x << endl;
	while (cl != l - 1 || cr != r) {
		// cout << cl << " " << cr << " " << sm << endl;
		if (sm < min(ai(cl), ai(cr))) {
			int v = gget(cl + 1, cr).y;
			change.push_back({v, x});
			// cout << "set up to " << u << " " << x << endl;
			if (ai(cl) <= ai(cr)) {
				sm += a[cl];
				--cl;
			} else {
				sm += a[cr];
				++cr;
			}
		}
		cl = glastgreater(l, cl + 1, sm);
		cr = gfirstgreater(cr - 1, r, sm);
		// cout << "got new sum " << sm << " " << cl << " " << cr << endl;
		sm = gsum(cl + 1, cr);
	}
}
 
int ai(int i) {
	if (i < 0 || i >= n) {
		return +INF;
	}
	return a[i];
}
 
vector<pair<int, int>> change;

int query(int l, int r) {
	change.clear();

	if (l) {
		loop_set_up(l, 0, n, 0, change);
		loop_set_up(l, l, r, 1, change);
	}
	if (r != n) {
		loop_set_up(r - 1, 0, n, 0, change);
		loop_set_up(r - 1, l, r, 1, change);
	}

	stable_sort(all(change), [](auto x, auto y) {
		return x.x < y.x;
	});
	reverse(all(change));
	change.resize(unique(all(change), [](auto x, auto y) {
		return x.x == y.x;
	}) - begin(change));

	assert(sz(change) < 120);

	for (auto &[where, what] : change) {
		int backup = up[where];
		set_up_to(where, what);
		what = backup;
	}
	auto [ansx, ansy] = tget(l, r);
	for (auto [where, what] : change) {
		set_up_to(where, what);
	}
	return ansx ? 0 : ansy;
}

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;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		g[N + i] = {a[i], i};
		gs[N + i] = a[i];
	}

	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]);
		mod[i] = 0;
	}
	for (int i = N; i--; ) {
		g[i] = max(g[2 * i], g[2 * i + 1]);
		gs[i] = gs[2 * i] + gs[2 * i + 1];
	}
 
	for (int i = 0; i < n; ++i) {
		left_[i] = glastgreater(0, i, a[i]);
		right_[i] = gfirstgreater(i + 1, n, a[i] - 1);
		if (gsum(left_[i] + 1, right_[i]) < min(ai(left_[i]), ai(right_[i])) &&
			(left_[i] != -1 || right_[i] != n)) {
			set_up_to(i, 1);
		}
	}
 
	int queries;
	cin >> queries;

	if (queries <= 1000) {
		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";
			}
		}
		return 0;
	}

	while (queries--) {
		int type, l, r;
		cin >> type >> l >> r;
		if (type == 1) {
			// a[l - 1] = r;
			// gset(l - 1, r);
			assert(0);
		} else {
			cout << query(l - 1, 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