oj.uz

Submission #899897

# Submission time Handle Problem Language Result Execution time Memory
899897 2024-01-07T09:02:08 Z TAhmed33 Fish 2 (JOI22_fish2) C++
8 / 100
 4000 ms 872892 KB 
#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

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 6492 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 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

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

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