답안 #899897

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899897	2024-01-07T09:02:08 Z	TAhmed33	Fish 2 (JOI22_fish2)	C++	8 / 100	4000 ms	872892 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];
}
map <pair <int, int>, int> memo;
int ans (int l, int r) {
	if (l > r) return 0;
	if (l == r) return 1;
	if (memo.count({l, r})) return memo[{l, r}];
	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 memo[{l, r}] = 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))]);
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int t, l, r;
		cin >> t >> l >> r;
		cout << ans(l, r) << '\n';
	}
}

Subtask #1

0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 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	6488 KB	Output is correct
2	Correct	15 ms	27812 KB	Output is correct
3	Correct	10 ms	27484 KB	Output is correct
4	Correct	15 ms	27804 KB	Output is correct
5	Correct	10 ms	27484 KB	Output is correct
6	Correct	24 ms	31104 KB	Output is correct
7	Correct	11 ms	27484 KB	Output is correct
8	Correct	25 ms	31016 KB	Output is correct
9	Correct	10 ms	27484 KB	Output is correct
10	Correct	14 ms	27808 KB	Output is correct
11	Correct	10 ms	27484 KB	Output is correct
12	Correct	10 ms	27524 KB	Output is correct
13	Correct	10 ms	27484 KB	Output is correct
14	Correct	17 ms	30040 KB	Output is correct
15	Correct	23 ms	30040 KB	Output is correct

Subtask #3

0 / 12.0

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

Subtask #4

0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6488 KB	Output is correct
2	Correct	15 ms	27812 KB	Output is correct
3	Correct	10 ms	27484 KB	Output is correct
4	Correct	15 ms	27804 KB	Output is correct
5	Correct	10 ms	27484 KB	Output is correct
6	Correct	24 ms	31104 KB	Output is correct
7	Correct	11 ms	27484 KB	Output is correct
8	Correct	25 ms	31016 KB	Output is correct
9	Correct	10 ms	27484 KB	Output is correct
10	Correct	14 ms	27808 KB	Output is correct
11	Correct	10 ms	27484 KB	Output is correct
12	Correct	10 ms	27524 KB	Output is correct
13	Correct	10 ms	27484 KB	Output is correct
14	Correct	17 ms	30040 KB	Output is correct
15	Correct	23 ms	30040 KB	Output is correct
16	Correct	1 ms	6488 KB	Output is correct
17	Correct	248 ms	45332 KB	Output is correct
18	Execution timed out	4097 ms	872892 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #5

0 / 35.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	6488 KB	Output is correct
2	Correct	15 ms	27812 KB	Output is correct
3	Correct	10 ms	27484 KB	Output is correct
4	Correct	15 ms	27804 KB	Output is correct
5	Correct	10 ms	27484 KB	Output is correct
6	Correct	24 ms	31104 KB	Output is correct
7	Correct	11 ms	27484 KB	Output is correct
8	Correct	25 ms	31016 KB	Output is correct
9	Correct	10 ms	27484 KB	Output is correct
10	Correct	14 ms	27808 KB	Output is correct
11	Correct	10 ms	27484 KB	Output is correct
12	Correct	10 ms	27524 KB	Output is correct
13	Correct	10 ms	27484 KB	Output is correct
14	Correct	17 ms	30040 KB	Output is correct
15	Correct	23 ms	30040 KB	Output is correct
16	Runtime error	6 ms	12892 KB	Execution killed with signal 11
17	Halted	0 ms	0 KB	-

Subtask #6

0 / 17.0

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