oj.uz

Submission #561683

# Submission time Handle Problem Language Result Execution time Memory
561683 2022-05-13T11:02:41 Z DanShaders Fish 2 (JOI22_fish2) C++17
8 / 100
 63 ms 8520 KB 
#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> 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];

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

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

pair<int, int> get_bounds(int i, ll s = -1) {
	if (s == -1) {
		s = a[i];
	}
	return {glastgreater(0, i, s), gfirstgreater(i, n, 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) {
		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);
		}
	}

	cout << t[0].y << "\n";

	// int queries;
	// cin >> queries;
	// 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 62 ms 8432 KB Output is correct
3 Correct 56 ms 8476 KB Output is correct
4 Correct 59 ms 8444 KB Output is correct
5 Correct 55 ms 8444 KB Output is correct
6 Correct 50 ms 8432 KB Output is correct
7 Correct 41 ms 8424 KB Output is correct
8 Correct 63 ms 8520 KB Output is correct
9 Correct 45 ms 8368 KB Output is correct
10 Correct 55 ms 8396 KB Output is correct
11 Correct 48 ms 8396 KB Output is correct
12 Correct 44 ms 8492 KB Output is correct
13 Correct 43 ms 8456 KB Output is correct
14 Correct 50 ms 8396 KB Output is correct
15 Correct 52 ms 8456 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3924 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 62 ms 8432 KB Output is correct
3 Correct 56 ms 8476 KB Output is correct
4 Correct 59 ms 8444 KB Output is correct
5 Correct 55 ms 8444 KB Output is correct
6 Correct 50 ms 8432 KB Output is correct
7 Correct 41 ms 8424 KB Output is correct
8 Correct 63 ms 8520 KB Output is correct
9 Correct 45 ms 8368 KB Output is correct
10 Correct 55 ms 8396 KB Output is correct
11 Correct 48 ms 8396 KB Output is correct
12 Correct 44 ms 8492 KB Output is correct
13 Correct 43 ms 8456 KB Output is correct
14 Correct 50 ms 8396 KB Output is correct
15 Correct 52 ms 8456 KB Output is correct
16 Incorrect 3 ms 3924 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3924 KB Output is correct
2 Correct 62 ms 8432 KB Output is correct
3 Correct 56 ms 8476 KB Output is correct
4 Correct 59 ms 8444 KB Output is correct
5 Correct 55 ms 8444 KB Output is correct
6 Correct 50 ms 8432 KB Output is correct
7 Correct 41 ms 8424 KB Output is correct
8 Correct 63 ms 8520 KB Output is correct
9 Correct 45 ms 8368 KB Output is correct
10 Correct 55 ms 8396 KB Output is correct
11 Correct 48 ms 8396 KB Output is correct
12 Correct 44 ms 8492 KB Output is correct
13 Correct 43 ms 8456 KB Output is correct
14 Correct 50 ms 8396 KB Output is correct
15 Correct 52 ms 8456 KB Output is correct
16 Incorrect 3 ms 3912 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3924 KB Output isn't correct
2 Halted 0 ms 0 KB -