oj.uz

Submission #860479

# Submission time Handle Problem Language Result Execution time Memory
860479 2023-10-13T05:57:33 Z Halym2007 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++11
100 / 100
 2833 ms 100692 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int NN = 1e7 + 5;
#define ff first
#define ss second
#define pb push_back
vector <pair <int, int>> v[N];
int a[N], k[N], ans[N], st[NN], jog;

void update (int ind, int l, int r, int pos, int val) {
	if (l == r) {
		st[ind] = max (st[ind], val);
		return;
	}
	if (pos <= (l + r) / 2) {
		update (ind * 2, l, (l + r) / 2, pos, val);
	}
	else {
		update (ind * 2 + 1, (l + r) / 2 + 1, r, pos, val);
	}
	st[ind] = max (st[ind * 2], st[ind * 2 + 1]);
}

void jogap (int ind, int l, int r, int x, int y) {
	if (x > r or l > y) return;
	if (x <= l and r <= y) {
		jog = max (jog, st[ind]);
		return;
	}
	jogap (ind * 2, l, (l + r) / 2, x, y);
	jogap (ind * 2 + 1, (l + r) / 2 + 1, r, x, y);
}


int main () {
//	freopen ("input.txt", "r", stdin);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; ++i) {
		int l, r;
		cin >> l >> r >> k[i];
		v[r].pb ({l, i});	
	}
//	cout << "sak";
//	return 0;
	stack <int> s;
	for (int i = 1; i <= n; ++i) {
		while (!s.empty() and a[s.top()] <= a[i]) s.pop();
		if (!s.empty()) {
			update (1, 1, n, s.top(), a[i] + a[s.top()]);
		}
		s.push (i);
		for (pair <int, int> x : v[i]) {
			// x bilen i aralyk
			jog = 0;
			jogap (1, 1, n, x.ff, i);
			if (k[x.ss] >= jog) {
				ans[x.ss] = 1;
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		cout << ans[i] << endl;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 8 ms 31532 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31444 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31528 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 8 ms 31532 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31444 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31528 KB Output is correct
11 Correct 12 ms 31580 KB Output is correct
12 Correct 15 ms 31540 KB Output is correct
13 Correct 14 ms 31580 KB Output is correct
14 Correct 18 ms 31836 KB Output is correct
15 Correct 18 ms 31820 KB Output is correct
16 Correct 16 ms 31580 KB Output is correct
17 Correct 15 ms 31736 KB Output is correct
18 Correct 16 ms 31580 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2750 ms 97484 KB Output is correct
2 Correct 2769 ms 98340 KB Output is correct
3 Correct 2718 ms 98372 KB Output is correct
4 Correct 2724 ms 98524 KB Output is correct
5 Correct 2603 ms 92332 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 251 ms 40576 KB Output is correct
2 Correct 219 ms 40016 KB Output is correct
3 Correct 216 ms 39508 KB Output is correct
4 Correct 227 ms 39548 KB Output is correct
5 Correct 222 ms 39508 KB Output is correct
6 Correct 200 ms 34704 KB Output is correct
7 Correct 199 ms 34620 KB Output is correct
8 Correct 207 ms 39084 KB Output is correct
9 Correct 180 ms 38136 KB Output is correct
10 Correct 202 ms 39212 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 8 ms 31532 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31444 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31528 KB Output is correct
11 Correct 12 ms 31580 KB Output is correct
12 Correct 15 ms 31540 KB Output is correct
13 Correct 14 ms 31580 KB Output is correct
14 Correct 18 ms 31836 KB Output is correct
15 Correct 18 ms 31820 KB Output is correct
16 Correct 16 ms 31580 KB Output is correct
17 Correct 15 ms 31736 KB Output is correct
18 Correct 16 ms 31580 KB Output is correct
19 Correct 508 ms 50696 KB Output is correct
20 Correct 503 ms 50256 KB Output is correct
21 Correct 486 ms 49304 KB Output is correct
22 Correct 481 ms 49032 KB Output is correct
23 Correct 480 ms 48976 KB Output is correct
24 Correct 460 ms 46880 KB Output is correct
25 Correct 471 ms 47188 KB Output is correct
26 Correct 467 ms 47444 KB Output is correct
27 Correct 482 ms 47568 KB Output is correct
28 Correct 476 ms 47868 KB Output is correct
29 Correct 479 ms 48208 KB Output is correct
30 Correct 483 ms 48208 KB Output is correct
31 Correct 485 ms 48720 KB Output is correct
32 Correct 506 ms 48212 KB Output is correct
33 Correct 488 ms 46052 KB Output is correct
34 Correct 496 ms 46416 KB Output is correct
35 Correct 445 ms 46480 KB Output is correct
36 Correct 465 ms 46544 KB Output is correct
37 Correct 446 ms 46484 KB Output is correct
38 Correct 480 ms 46460 KB Output is correct
39 Correct 448 ms 47636 KB Output is correct
40 Correct 405 ms 45504 KB Output is correct
41 Correct 445 ms 46184 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31324 KB Output is correct
2 Correct 6 ms 31324 KB Output is correct
3 Correct 7 ms 31324 KB Output is correct
4 Correct 7 ms 31324 KB Output is correct
5 Correct 6 ms 31324 KB Output is correct
6 Correct 8 ms 31532 KB Output is correct
7 Correct 7 ms 31324 KB Output is correct
8 Correct 7 ms 31444 KB Output is correct
9 Correct 7 ms 31324 KB Output is correct
10 Correct 7 ms 31528 KB Output is correct
11 Correct 12 ms 31580 KB Output is correct
12 Correct 15 ms 31540 KB Output is correct
13 Correct 14 ms 31580 KB Output is correct
14 Correct 18 ms 31836 KB Output is correct
15 Correct 18 ms 31820 KB Output is correct
16 Correct 16 ms 31580 KB Output is correct
17 Correct 15 ms 31736 KB Output is correct
18 Correct 16 ms 31580 KB Output is correct
19 Correct 2750 ms 97484 KB Output is correct
20 Correct 2769 ms 98340 KB Output is correct
21 Correct 2718 ms 98372 KB Output is correct
22 Correct 2724 ms 98524 KB Output is correct
23 Correct 2603 ms 92332 KB Output is correct
24 Correct 251 ms 40576 KB Output is correct
25 Correct 219 ms 40016 KB Output is correct
26 Correct 216 ms 39508 KB Output is correct
27 Correct 227 ms 39548 KB Output is correct
28 Correct 222 ms 39508 KB Output is correct
29 Correct 200 ms 34704 KB Output is correct
30 Correct 199 ms 34620 KB Output is correct
31 Correct 207 ms 39084 KB Output is correct
32 Correct 180 ms 38136 KB Output is correct
33 Correct 202 ms 39212 KB Output is correct
34 Correct 508 ms 50696 KB Output is correct
35 Correct 503 ms 50256 KB Output is correct
36 Correct 486 ms 49304 KB Output is correct
37 Correct 481 ms 49032 KB Output is correct
38 Correct 480 ms 48976 KB Output is correct
39 Correct 460 ms 46880 KB Output is correct
40 Correct 471 ms 47188 KB Output is correct
41 Correct 467 ms 47444 KB Output is correct
42 Correct 482 ms 47568 KB Output is correct
43 Correct 476 ms 47868 KB Output is correct
44 Correct 479 ms 48208 KB Output is correct
45 Correct 483 ms 48208 KB Output is correct
46 Correct 485 ms 48720 KB Output is correct
47 Correct 506 ms 48212 KB Output is correct
48 Correct 488 ms 46052 KB Output is correct
49 Correct 496 ms 46416 KB Output is correct
50 Correct 445 ms 46480 KB Output is correct
51 Correct 465 ms 46544 KB Output is correct
52 Correct 446 ms 46484 KB Output is correct
53 Correct 480 ms 46460 KB Output is correct
54 Correct 448 ms 47636 KB Output is correct
55 Correct 405 ms 45504 KB Output is correct
56 Correct 445 ms 46184 KB Output is correct
57 Correct 2714 ms 100204 KB Output is correct
58 Correct 2833 ms 100692 KB Output is correct
59 Correct 2712 ms 97412 KB Output is correct
60 Correct 2659 ms 97436 KB Output is correct
61 Correct 2668 ms 97500 KB Output is correct
62 Correct 2667 ms 97164 KB Output is correct
63 Correct 2276 ms 83388 KB Output is correct
64 Correct 2287 ms 83924 KB Output is correct
65 Correct 2490 ms 89108 KB Output is correct
66 Correct 2480 ms 88908 KB Output is correct
67 Correct 2547 ms 88920 KB Output is correct
68 Correct 2552 ms 91860 KB Output is correct
69 Correct 2580 ms 91960 KB Output is correct
70 Correct 2599 ms 91240 KB Output is correct
71 Correct 2625 ms 91504 KB Output is correct
72 Correct 2575 ms 91336 KB Output is correct
73 Correct 2253 ms 82692 KB Output is correct
74 Correct 2253 ms 83956 KB Output is correct
75 Correct 2268 ms 82640 KB Output is correct
76 Correct 2215 ms 83116 KB Output is correct
77 Correct 2338 ms 82352 KB Output is correct
78 Correct 2420 ms 86852 KB Output is correct
79 Correct 2142 ms 77144 KB Output is correct
80 Correct 2323 ms 81912 KB Output is correct