Submission #561766

#	Time	Username	Problem	Language	Result	Execution time	Memory
561766		DanShaders	Fish 2 (JOI22_fish2)	C++17	48 / 100	4057 ms	9704 KiB

fish2

//bs:sanitizers
#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) {
	g[i + N] = {x, i};
	i += N;
	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];

struct S {
	int i, x, cl, cr;

	bool operator<(const S &other) const {
		return i < other.i;
	}

	bool operator==(const S &other) const {
		return i == other.i;
	}
};

void set_up_to(const S &s) {
	if (up[s.i] != s.x) {
		up[s.i] = s.x;
		// cout << "tadd " << s.cl + 1 << " " << s.cr << " " << (s.x ? 1 : -1) << endl;
		if (!s.x) {
			tadd(s.cl + 1, s.cr, -1);
		} else {
			tadd(s.cl + 1, s.cr, 1);
		}
	}
}

void loop_set_up(int u, int l, int r, int x, vector<S> &change) {
	if (!(l <= u && u < r)) {
		return;
	}
	auto ai = [&](int i) {
		if (i < l || i >= r) {
			return +INF;
		}
		return a[i];
	};

	int cl = glastgreater(l, u, a[u]),
		cr = gfirstgreater(u + 1, r, a[u] - 1);
	ll sm = gsum(cl + 1, cr);
	while (cl != l - 1 || cr != r) {
		if (sm < min(ai(cl), ai(cr))) {
			int v = gget(cl + 1, cr).y;
			// cout << "set " << cl << " " << cr << " " << v << endl;
			change.push_back({v, x, cl, cr});
			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);
		sm = gsum(cl + 1, cr);
	}
}

int ai(int i) {
	if (i < 0 || i >= n) {
		return +INF;
	}
	return a[i];
}

vector<S> 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));
	reverse(all(change));
	change.resize(unique(all(change)) - begin(change));

	for (auto &s : change) {
		// cout << "temp " << s.cl << " " << s.cr << " " << s.i << " " << s.x << endl;
		int backup = up[s.i];
		set_up_to(s);
		s.x = backup;
	}
	auto [ansx, ansy] = tget(l, r);
	// cout << ansx << " " << ansy << endl;
	for (const auto &s : change) {
		set_up_to(s);
	}
	return ansx ? 0 : ansy;
}

void aset(int i, int x) {
	int cl = glastgreater(0, i, a[i]),
		cr = gfirstgreater(i + 1, n, a[i] - 1),
		nl = glastgreater(0, i, x),
		nr = gfirstgreater(i + 1, n, x - 1);
	// cout << cr << endl;
	int clef = gget(cl + 1, i).y, crig = gget(i + 1, cr).y,
		nlef = gget(nl + 1, i).y, nrig = gget(i + 1, nr).y;

	// cout << "counted " << clef << " " << crig << " " << nlef << " " << nrig << endl;

	change.clear();
	loop_set_up(i, 0, n, 0, change);
	loop_set_up(cl, 0, n, 0, change);
	loop_set_up(cr, 0, n, 0, change);
	loop_set_up(clef, 0, n, 0, change);
	loop_set_up(crig, 0, n, 0, change);
	loop_set_up(nl, 0, n, 0, change);
	loop_set_up(nr, 0, n, 0, change);
	loop_set_up(nlef, 0, n, 0, change);
	loop_set_up(nrig, 0, n, 0, change);

	stable_sort(all(change));
	reverse(all(change));
	change.resize(unique(all(change)) - begin(change));
	for (auto s : change) {
		// cout << "rollback " << s.cl << " " << s.cr << " " << s.i << " " << s.x << endl;
		set_up_to(s);
	}

	a[i] = x;
	gset(i, x);

	change.clear();
	loop_set_up(i, 0, n, 1, change);
	loop_set_up(cl, 0, n, 1, change);
	loop_set_up(cr, 0, n, 1, change);
	loop_set_up(clef, 0, n, 1, change);
	loop_set_up(crig, 0, n, 1, change);
	loop_set_up(nl, 0, n, 1, change);
	loop_set_up(nr, 0, n, 1, change);
	loop_set_up(nlef, 0, n, 1, change);
	loop_set_up(nrig, 0, n, 1, change);

	stable_sort(all(change));
	reverse(all(change));
	change.resize(unique(all(change)) - begin(change));
	for (auto s : change) {
		// cout << "apply " << s.cl << " " << s.cr << " " << s.i << " " << s.x << endl;
		set_up_to(s);
	}
}

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) {
		int cl = glastgreater(0, i, a[i]);
		int cr = gfirstgreater(i + 1, n, a[i] - 1);
		if (gsum(cl + 1, cr) < min(ai(cl), ai(cr)) &&
			(cl != -1 || cr != n)) {
			set_up_to({i, 1, cl, cr});
		}
	}

	int queries;
	cin >> queries;
	while (queries--) {
		int type, l, r;
		cin >> type >> l >> r;
		if (type == 1) {
			aset(l - 1, r);
		} else {
			cout << query(l - 1, r) << "\n";
		}
	}
}

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