oj.uz

Submission #561744

# Submission time Handle Problem Language Result Execution time Memory
561744 2022-05-13T12:30:55 Z DanShaders Fish 2 (JOI22_fish2) C++17
31 / 100
 3839 ms 9264 KB 
//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;
		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 (u == -1) {
		return;
	}
	assert(l <= u && u < r);
	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 << 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) {
		int backup = up[s.i];
		set_up_to(s);
		s.x = backup;
	}
	auto [ansx, ansy] = tget(l, r);
	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 << cl << " " << cr << " " << nl << " " << nr << 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 << clef << " " << crig << " " << nlef << " " << nrig << endl;
	if (clef == -1) {
		clef = i;
	} else if (crig == -1) {
		crig = i;
	}
	if (nlef == -1) {
		nlef = i;
	} else if (nrig == -1) {
		nrig = i;
	}

	change.clear();

	loop_set_up(clef, 0, n, 0, change);
	loop_set_up(crig, 0, n, 0, change);
	loop_set_up(nlef, 0, n, 0, change);
	loop_set_up(nrig, 0, n, 0, change);

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

	loop_set_up(clef, 0, n, 1, change);
	loop_set_up(crig, 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 << s.i << " " << s.x << " " << s.cl << " " << s.cr << 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Incorrect 15 ms 3980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3924 KB Output is correct
2 Correct 59 ms 7872 KB Output is correct
3 Correct 58 ms 7756 KB Output is correct
4 Correct 61 ms 7956 KB Output is correct
5 Correct 61 ms 7756 KB Output is correct
6 Correct 49 ms 8292 KB Output is correct
7 Correct 41 ms 7628 KB Output is correct
8 Correct 51 ms 8348 KB Output is correct
9 Correct 43 ms 7600 KB Output is correct
10 Correct 59 ms 7924 KB Output is correct
11 Correct 50 ms 7628 KB Output is correct
12 Correct 49 ms 7644 KB Output is correct
13 Correct 47 ms 7600 KB Output is correct
14 Correct 54 ms 8000 KB Output is correct
15 Correct 55 ms 7916 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Incorrect 15 ms 3980 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3924 KB Output is correct
2 Correct 59 ms 7872 KB Output is correct
3 Correct 58 ms 7756 KB Output is correct
4 Correct 61 ms 7956 KB Output is correct
5 Correct 61 ms 7756 KB Output is correct
6 Correct 49 ms 8292 KB Output is correct
7 Correct 41 ms 7628 KB Output is correct
8 Correct 51 ms 8348 KB Output is correct
9 Correct 43 ms 7600 KB Output is correct
10 Correct 59 ms 7924 KB Output is correct
11 Correct 50 ms 7628 KB Output is correct
12 Correct 49 ms 7644 KB Output is correct
13 Correct 47 ms 7600 KB Output is correct
14 Correct 54 ms 8000 KB Output is correct
15 Correct 55 ms 7916 KB Output is correct
16 Correct 3 ms 3924 KB Output is correct
17 Correct 1971 ms 9020 KB Output is correct
18 Correct 1788 ms 8788 KB Output is correct
19 Correct 1978 ms 8740 KB Output is correct
20 Correct 2592 ms 8900 KB Output is correct
21 Correct 1894 ms 8804 KB Output is correct
22 Correct 1779 ms 8816 KB Output is correct
23 Correct 1899 ms 8820 KB Output is correct
24 Correct 2597 ms 8716 KB Output is correct
25 Correct 1898 ms 8752 KB Output is correct
26 Correct 2607 ms 9004 KB Output is correct
27 Correct 465 ms 8800 KB Output is correct
28 Correct 496 ms 8900 KB Output is correct
29 Correct 457 ms 8908 KB Output is correct
30 Correct 2283 ms 8732 KB Output is correct
31 Correct 2475 ms 8528 KB Output is correct
32 Correct 3839 ms 8872 KB Output is correct
33 Correct 1277 ms 8816 KB Output is correct
34 Correct 3827 ms 8708 KB Output is correct
35 Correct 2154 ms 8740 KB Output is correct
36 Correct 2729 ms 8980 KB Output is correct
37 Correct 854 ms 8648 KB Output is correct
38 Correct 833 ms 8828 KB Output is correct
39 Correct 686 ms 8820 KB Output is correct
40 Correct 635 ms 8848 KB Output is correct

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3924 KB Output is correct
2 Correct 59 ms 7872 KB Output is correct
3 Correct 58 ms 7756 KB Output is correct
4 Correct 61 ms 7956 KB Output is correct
5 Correct 61 ms 7756 KB Output is correct
6 Correct 49 ms 8292 KB Output is correct
7 Correct 41 ms 7628 KB Output is correct
8 Correct 51 ms 8348 KB Output is correct
9 Correct 43 ms 7600 KB Output is correct
10 Correct 59 ms 7924 KB Output is correct
11 Correct 50 ms 7628 KB Output is correct
12 Correct 49 ms 7644 KB Output is correct
13 Correct 47 ms 7600 KB Output is correct
14 Correct 54 ms 8000 KB Output is correct
15 Correct 55 ms 7916 KB Output is correct
16 Correct 3 ms 3924 KB Output is correct
17 Incorrect 2484 ms 9264 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 2 ms 3924 KB Output is correct
3 Correct 2 ms 3924 KB Output is correct
4 Correct 2 ms 3924 KB Output is correct
5 Incorrect 15 ms 3980 KB Output isn't correct
6 Halted 0 ms 0 KB -