oj.uz

Submission #555775

# Submission time Handle Problem Language Result Execution time Memory
555775 2022-05-01T14:02:05 Z ngpin04 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
100 / 100
 1046 ms 134936 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1e6 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> ind[N];
vector <int> qr[N];

int bit[N];
int ans[N];
int a[N];
int r[N];
int w[N];
int n,q;

void update(int pos, int val) {
	for (; pos <= n; pos += pos & -pos)
		maxi(bit[pos], val);
}

int getmax(int pos) {
	int res = 0;
	for (; pos; pos -= pos & -pos)
		maxi(res, bit[pos]);
	return res;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	cin >> n >> q;
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	for (int i = 1; i <= q; i++) {
		int l;
		cin >> l >> r[i] >> w[i];
		qr[l].push_back(i);
	}

	a[0] = 2 * oo;
	vector <int> s(1, 0);
	for (int i = 1; i <= n; i++) {
		while (s.size() && a[i] >= a[s.back()])
			s.pop_back();
		ind[s.back()].push_back(i);
		s.push_back(i);
	}

	for (int i = n; i >= 1; i--) {
		for (int j : ind[i])
			update(j, a[i] + a[j]);

		for (int id : qr[i]) 
			ans[id] = (getmax(r[id]) <= w[id]);
	}

	for (int i = 1; i <= q; i++)
		cout << ans[i] << "\n";
	return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 27 ms 47296 KB Output is correct
3 Correct 23 ms 47272 KB Output is correct
4 Correct 25 ms 47212 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 24 ms 47316 KB Output is correct
8 Correct 27 ms 47336 KB Output is correct
9 Correct 23 ms 47332 KB Output is correct
10 Correct 23 ms 47316 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 27 ms 47296 KB Output is correct
3 Correct 23 ms 47272 KB Output is correct
4 Correct 25 ms 47212 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 24 ms 47316 KB Output is correct
8 Correct 27 ms 47336 KB Output is correct
9 Correct 23 ms 47332 KB Output is correct
10 Correct 23 ms 47316 KB Output is correct
11 Correct 25 ms 47380 KB Output is correct
12 Correct 25 ms 47584 KB Output is correct
13 Correct 28 ms 47640 KB Output is correct
14 Correct 30 ms 47748 KB Output is correct
15 Correct 28 ms 47676 KB Output is correct
16 Correct 27 ms 47604 KB Output is correct
17 Correct 24 ms 47552 KB Output is correct
18 Correct 32 ms 47696 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 134936 KB Output is correct
2 Correct 969 ms 127452 KB Output is correct
3 Correct 968 ms 127360 KB Output is correct
4 Correct 974 ms 127652 KB Output is correct
5 Correct 866 ms 111504 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 54988 KB Output is correct
2 Correct 80 ms 53784 KB Output is correct
3 Correct 73 ms 53280 KB Output is correct
4 Correct 75 ms 53484 KB Output is correct
5 Correct 76 ms 53560 KB Output is correct
6 Correct 62 ms 52008 KB Output is correct
7 Correct 64 ms 51948 KB Output is correct
8 Correct 69 ms 52788 KB Output is correct
9 Correct 54 ms 50536 KB Output is correct
10 Correct 70 ms 52640 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 27 ms 47296 KB Output is correct
3 Correct 23 ms 47272 KB Output is correct
4 Correct 25 ms 47212 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 24 ms 47316 KB Output is correct
8 Correct 27 ms 47336 KB Output is correct
9 Correct 23 ms 47332 KB Output is correct
10 Correct 23 ms 47316 KB Output is correct
11 Correct 25 ms 47380 KB Output is correct
12 Correct 25 ms 47584 KB Output is correct
13 Correct 28 ms 47640 KB Output is correct
14 Correct 30 ms 47748 KB Output is correct
15 Correct 28 ms 47676 KB Output is correct
16 Correct 27 ms 47604 KB Output is correct
17 Correct 24 ms 47552 KB Output is correct
18 Correct 32 ms 47696 KB Output is correct
19 Correct 183 ms 65364 KB Output is correct
20 Correct 176 ms 65356 KB Output is correct
21 Correct 153 ms 62860 KB Output is correct
22 Correct 152 ms 62668 KB Output is correct
23 Correct 147 ms 62684 KB Output is correct
24 Correct 129 ms 59700 KB Output is correct
25 Correct 133 ms 59568 KB Output is correct
26 Correct 141 ms 60480 KB Output is correct
27 Correct 151 ms 60484 KB Output is correct
28 Correct 149 ms 60944 KB Output is correct
29 Correct 169 ms 62276 KB Output is correct
30 Correct 162 ms 62216 KB Output is correct
31 Correct 157 ms 62136 KB Output is correct
32 Correct 161 ms 62232 KB Output is correct
33 Correct 155 ms 62156 KB Output is correct
34 Correct 125 ms 59044 KB Output is correct
35 Correct 134 ms 59072 KB Output is correct
36 Correct 121 ms 58928 KB Output is correct
37 Correct 124 ms 58816 KB Output is correct
38 Correct 125 ms 59032 KB Output is correct
39 Correct 143 ms 60360 KB Output is correct
40 Correct 128 ms 58176 KB Output is correct
41 Correct 143 ms 59600 KB Output is correct

Subtask #6
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 47308 KB Output is correct
2 Correct 27 ms 47296 KB Output is correct
3 Correct 23 ms 47272 KB Output is correct
4 Correct 25 ms 47212 KB Output is correct
5 Correct 24 ms 47276 KB Output is correct
6 Correct 22 ms 47316 KB Output is correct
7 Correct 24 ms 47316 KB Output is correct
8 Correct 27 ms 47336 KB Output is correct
9 Correct 23 ms 47332 KB Output is correct
10 Correct 23 ms 47316 KB Output is correct
11 Correct 25 ms 47380 KB Output is correct
12 Correct 25 ms 47584 KB Output is correct
13 Correct 28 ms 47640 KB Output is correct
14 Correct 30 ms 47748 KB Output is correct
15 Correct 28 ms 47676 KB Output is correct
16 Correct 27 ms 47604 KB Output is correct
17 Correct 24 ms 47552 KB Output is correct
18 Correct 32 ms 47696 KB Output is correct
19 Correct 1020 ms 134936 KB Output is correct
20 Correct 969 ms 127452 KB Output is correct
21 Correct 968 ms 127360 KB Output is correct
22 Correct 974 ms 127652 KB Output is correct
23 Correct 866 ms 111504 KB Output is correct
24 Correct 86 ms 54988 KB Output is correct
25 Correct 80 ms 53784 KB Output is correct
26 Correct 73 ms 53280 KB Output is correct
27 Correct 75 ms 53484 KB Output is correct
28 Correct 76 ms 53560 KB Output is correct
29 Correct 62 ms 52008 KB Output is correct
30 Correct 64 ms 51948 KB Output is correct
31 Correct 69 ms 52788 KB Output is correct
32 Correct 54 ms 50536 KB Output is correct
33 Correct 70 ms 52640 KB Output is correct
34 Correct 183 ms 65364 KB Output is correct
35 Correct 176 ms 65356 KB Output is correct
36 Correct 153 ms 62860 KB Output is correct
37 Correct 152 ms 62668 KB Output is correct
38 Correct 147 ms 62684 KB Output is correct
39 Correct 129 ms 59700 KB Output is correct
40 Correct 133 ms 59568 KB Output is correct
41 Correct 141 ms 60480 KB Output is correct
42 Correct 151 ms 60484 KB Output is correct
43 Correct 149 ms 60944 KB Output is correct
44 Correct 169 ms 62276 KB Output is correct
45 Correct 162 ms 62216 KB Output is correct
46 Correct 157 ms 62136 KB Output is correct
47 Correct 161 ms 62232 KB Output is correct
48 Correct 155 ms 62156 KB Output is correct
49 Correct 125 ms 59044 KB Output is correct
50 Correct 134 ms 59072 KB Output is correct
51 Correct 121 ms 58928 KB Output is correct
52 Correct 124 ms 58816 KB Output is correct
53 Correct 125 ms 59032 KB Output is correct
54 Correct 143 ms 60360 KB Output is correct
55 Correct 128 ms 58176 KB Output is correct
56 Correct 143 ms 59600 KB Output is correct
57 Correct 1046 ms 126912 KB Output is correct
58 Correct 1006 ms 127324 KB Output is correct
59 Correct 930 ms 121684 KB Output is correct
60 Correct 934 ms 121576 KB Output is correct
61 Correct 961 ms 121664 KB Output is correct
62 Correct 944 ms 121804 KB Output is correct
63 Correct 592 ms 106280 KB Output is correct
64 Correct 614 ms 106232 KB Output is correct
65 Correct 846 ms 105452 KB Output is correct
66 Correct 841 ms 105244 KB Output is correct
67 Correct 843 ms 105896 KB Output is correct
68 Correct 874 ms 111680 KB Output is correct
69 Correct 876 ms 111588 KB Output is correct
70 Correct 883 ms 110996 KB Output is correct
71 Correct 872 ms 110888 KB Output is correct
72 Correct 926 ms 111128 KB Output is correct
73 Correct 548 ms 104900 KB Output is correct
74 Correct 572 ms 105664 KB Output is correct
75 Correct 561 ms 104672 KB Output is correct
76 Correct 557 ms 104748 KB Output is correct
77 Correct 594 ms 104940 KB Output is correct
78 Correct 753 ms 114272 KB Output is correct
79 Correct 591 ms 99968 KB Output is correct
80 Correct 757 ms 110112 KB Output is correct