Submission #887267

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
887267	2023-12-14T07:08:23 Z	alex_2008	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	60 ms	97372 KB

sortbooks

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <fstream>
#include <bitset>
typedef long long ll;
using namespace std;
const int N = 5e3 + 10;
int a[N], l[N];
int ans[N][N];
int main() {
	int n, q;
	cin >> n >> q;
	a[0] = 1e9 + 10;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		l[i] = i - 1;
		while (a[i] >= a[l[i]]) {
			l[i] = l[l[i]];
		}
	}
	for (int i = 1; i <= n; i++) {
		ans[i][i] = 0;
		for (int j = i + 1; j <= n; j++) {
			ans[i][j] = ans[i][j - 1];
			if (l[j] >= i) ans[i][j] = max(ans[i][j], a[l[j]] + a[j]);
		}
	}
	while (q--) {
		int l, r, k;
		cin >> l >> r >> k;
		if (ans[l][r] <= k) cout << "1\n";
		else cout << "0\n";
	}
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	448 KB	Output is correct
3	Correct	2 ms	4444 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	4544 KB	Output is correct
6	Correct	3 ms	10588 KB	Output is correct
7	Correct	3 ms	10588 KB	Output is correct
8	Correct	3 ms	10688 KB	Output is correct
9	Correct	3 ms	6492 KB	Output is correct
10	Correct	4 ms	10596 KB	Output is correct

Subtask #2

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	448 KB	Output is correct
3	Correct	2 ms	4444 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	4544 KB	Output is correct
6	Correct	3 ms	10588 KB	Output is correct
7	Correct	3 ms	10588 KB	Output is correct
8	Correct	3 ms	10688 KB	Output is correct
9	Correct	3 ms	6492 KB	Output is correct
10	Correct	4 ms	10596 KB	Output is correct
11	Correct	15 ms	29276 KB	Output is correct
12	Correct	59 ms	97140 KB	Output is correct
13	Correct	47 ms	97144 KB	Output is correct
14	Correct	60 ms	97364 KB	Output is correct
15	Correct	51 ms	97372 KB	Output is correct
16	Correct	53 ms	97360 KB	Output is correct
17	Correct	37 ms	82776 KB	Output is correct
18	Correct	48 ms	97260 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	604 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	4 ms	604 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	448 KB	Output is correct
3	Correct	2 ms	4444 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	4544 KB	Output is correct
6	Correct	3 ms	10588 KB	Output is correct
7	Correct	3 ms	10588 KB	Output is correct
8	Correct	3 ms	10688 KB	Output is correct
9	Correct	3 ms	6492 KB	Output is correct
10	Correct	4 ms	10596 KB	Output is correct
11	Correct	15 ms	29276 KB	Output is correct
12	Correct	59 ms	97140 KB	Output is correct
13	Correct	47 ms	97144 KB	Output is correct
14	Correct	60 ms	97364 KB	Output is correct
15	Correct	51 ms	97372 KB	Output is correct
16	Correct	53 ms	97360 KB	Output is correct
17	Correct	37 ms	82776 KB	Output is correct
18	Correct	48 ms	97260 KB	Output is correct
19	Runtime error	6 ms	604 KB	Execution killed with signal 11
20	Halted	0 ms	0 KB	-

Subtask #6

0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	448 KB	Output is correct
3	Correct	2 ms	4444 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	4544 KB	Output is correct
6	Correct	3 ms	10588 KB	Output is correct
7	Correct	3 ms	10588 KB	Output is correct
8	Correct	3 ms	10688 KB	Output is correct
9	Correct	3 ms	6492 KB	Output is correct
10	Correct	4 ms	10596 KB	Output is correct
11	Correct	15 ms	29276 KB	Output is correct
12	Correct	59 ms	97140 KB	Output is correct
13	Correct	47 ms	97144 KB	Output is correct
14	Correct	60 ms	97364 KB	Output is correct
15	Correct	51 ms	97372 KB	Output is correct
16	Correct	53 ms	97360 KB	Output is correct
17	Correct	37 ms	82776 KB	Output is correct
18	Correct	48 ms	97260 KB	Output is correct
19	Runtime error	4 ms	604 KB	Execution killed with signal 11
20	Halted	0 ms	0 KB	-