답안 #899895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899895	2024-01-07T08:59:10 Z	TAhmed33	Fish 2 (JOI22_fish2)	C++	8 / 100	15 ms	28500 KB

fish2

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 25;
pair <int, int> sparse[17][MAXN];
int a[MAXN], n;
int pref[MAXN];
pair <int, int> query (int l, int r) {
	int m = __lg(r - l + 1);
	auto x = max(sparse[m][l], sparse[m][r - (1 << m) + 1]);
	x.second *= -1;
	return x;
}
int get (int l, int r) {
	if (l > r) return 0;
	return pref[r] - pref[l - 1];
}
int ans (int l, int r) {
	if (l > r) return 0;
	if (l == r) return 1;
	auto u = query(l, r);
	int ret = 1;
	if (get(l, u.second - 1) >= a[u.second]) ret += ans(l, u.second - 1);
	if (get(u.second + 1, r) >= a[u.second]) ret += ans(u.second + 1, r);
	return ret; 
}
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		sparse[0][i] = {a[i], -i};
		pref[i] = a[i] + pref[i - 1];
	}
	for (int i = 1; i < 17; i++) {
		for (int j = 1; j + (1 << i) - 1 <= n; j++) {
			sparse[i][j] = max(sparse[i - 1][j], sparse[i - 1][j + (1 << (i - 1))]);
		}
	}
	cout << ans(1, n) << '\n';
}

Subtask #1

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	6492 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	11 ms	27484 KB	Output is correct
3	Correct	10 ms	27860 KB	Output is correct
4	Correct	12 ms	27996 KB	Output is correct
5	Correct	10 ms	27736 KB	Output is correct
6	Correct	15 ms	28416 KB	Output is correct
7	Correct	13 ms	27740 KB	Output is correct
8	Correct	15 ms	28500 KB	Output is correct
9	Correct	10 ms	27740 KB	Output is correct
10	Correct	12 ms	28152 KB	Output is correct
11	Correct	10 ms	27740 KB	Output is correct
12	Correct	10 ms	27784 KB	Output is correct
13	Correct	10 ms	27740 KB	Output is correct
14	Correct	13 ms	28172 KB	Output is correct
15	Correct	14 ms	27996 KB	Output is correct

Subtask #3

0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	6492 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	11 ms	27484 KB	Output is correct
3	Correct	10 ms	27860 KB	Output is correct
4	Correct	12 ms	27996 KB	Output is correct
5	Correct	10 ms	27736 KB	Output is correct
6	Correct	15 ms	28416 KB	Output is correct
7	Correct	13 ms	27740 KB	Output is correct
8	Correct	15 ms	28500 KB	Output is correct
9	Correct	10 ms	27740 KB	Output is correct
10	Correct	12 ms	28152 KB	Output is correct
11	Correct	10 ms	27740 KB	Output is correct
12	Correct	10 ms	27784 KB	Output is correct
13	Correct	10 ms	27740 KB	Output is correct
14	Correct	13 ms	28172 KB	Output is correct
15	Correct	14 ms	27996 KB	Output is correct
16	Incorrect	1 ms	6488 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #5

0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6492 KB	Output is correct
2	Correct	11 ms	27484 KB	Output is correct
3	Correct	10 ms	27860 KB	Output is correct
4	Correct	12 ms	27996 KB	Output is correct
5	Correct	10 ms	27736 KB	Output is correct
6	Correct	15 ms	28416 KB	Output is correct
7	Correct	13 ms	27740 KB	Output is correct
8	Correct	15 ms	28500 KB	Output is correct
9	Correct	10 ms	27740 KB	Output is correct
10	Correct	12 ms	28152 KB	Output is correct
11	Correct	10 ms	27740 KB	Output is correct
12	Correct	10 ms	27784 KB	Output is correct
13	Correct	10 ms	27740 KB	Output is correct
14	Correct	13 ms	28172 KB	Output is correct
15	Correct	14 ms	27996 KB	Output is correct
16	Incorrect	1 ms	6492 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1 ms	6492 KB	Output isn't correct
2	Halted	0 ms	0 KB	-