#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int MAXN = (int)(1e6) + 5;
struct Query {
int l, i, k;
};
int arr[MAXN];
bool ans[MAXN];
vector<Query> qs[MAXN];
int seg[4*MAXN];
void upd(int i, int val, int n = 1, int tl = 0, int tr = MAXN-1) {
if (tl == tr) {
seg[n] = val;
}
else {
int tm = (tl + tr)/2;
if (i <= tm) {
upd(i, val, 2*n, tl, tm);
}
else {
upd(i, val, 2*n+1, tm+1, tr);
}
seg[n] = max(seg[2*n], seg[2*n+1]);
}
}
int query(int l, int r, int n = 1, int tl = 0, int tr = MAXN-1) {
if (l > tr || r < tl) {
return 0;
}
else if (l <= tl && tr <= r) {
return seg[n];
}
else {
int tm = (tl + tr)/2;
return max(query(l, r, 2*n, tl, tm), query(l, r, 2*n+1, tm+1, tr));
}
}
int main() {
cin.tie(0);
cin.sync_with_stdio(0);
int N, M;
cin >> N >> M;
FR(i, N) cin >> arr[i];
deque<pair<int, int>> deq;
deq.push_back({arr[0], 0});
FR(i, M) {
int l, r, k;
cin >> l >> r >> k;
l--, r--;
qs[r].push_back({l, i, k});
}
for (int i = 0; i < N; i++) {
while (deq.size() && deq.back().first <= arr[i]) {
deq.pop_back();
}
if (deq.size()) {
upd(deq.back().second, deq.back().first+arr[i]);
}
deq.push_back({arr[i], i});
for (Query q : qs[i]) {
ans[q.i] = (query(q.l, i) <= q.k);
}
}
for (int i = 0; i < M; i++) {
cout << ans[i] << '\n';
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Correct |
16 ms |
23788 KB |
Output is correct |
3 |
Correct |
17 ms |
23916 KB |
Output is correct |
4 |
Correct |
17 ms |
24044 KB |
Output is correct |
5 |
Correct |
17 ms |
23916 KB |
Output is correct |
6 |
Correct |
17 ms |
23916 KB |
Output is correct |
7 |
Correct |
19 ms |
23916 KB |
Output is correct |
8 |
Correct |
17 ms |
23916 KB |
Output is correct |
9 |
Correct |
17 ms |
23916 KB |
Output is correct |
10 |
Correct |
17 ms |
23916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Correct |
16 ms |
23788 KB |
Output is correct |
3 |
Correct |
17 ms |
23916 KB |
Output is correct |
4 |
Correct |
17 ms |
24044 KB |
Output is correct |
5 |
Correct |
17 ms |
23916 KB |
Output is correct |
6 |
Correct |
17 ms |
23916 KB |
Output is correct |
7 |
Correct |
19 ms |
23916 KB |
Output is correct |
8 |
Correct |
17 ms |
23916 KB |
Output is correct |
9 |
Correct |
17 ms |
23916 KB |
Output is correct |
10 |
Correct |
17 ms |
23916 KB |
Output is correct |
11 |
Correct |
19 ms |
24044 KB |
Output is correct |
12 |
Correct |
20 ms |
24172 KB |
Output is correct |
13 |
Correct |
22 ms |
24204 KB |
Output is correct |
14 |
Correct |
23 ms |
24300 KB |
Output is correct |
15 |
Correct |
23 ms |
24300 KB |
Output is correct |
16 |
Correct |
21 ms |
24172 KB |
Output is correct |
17 |
Correct |
20 ms |
24172 KB |
Output is correct |
18 |
Correct |
21 ms |
24172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1707 ms |
60848 KB |
Output is correct |
2 |
Correct |
1729 ms |
75228 KB |
Output is correct |
3 |
Correct |
1729 ms |
75084 KB |
Output is correct |
4 |
Correct |
1702 ms |
74980 KB |
Output is correct |
5 |
Correct |
1398 ms |
66796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
136 ms |
27500 KB |
Output is correct |
2 |
Correct |
130 ms |
29292 KB |
Output is correct |
3 |
Correct |
116 ms |
28524 KB |
Output is correct |
4 |
Correct |
122 ms |
28780 KB |
Output is correct |
5 |
Correct |
119 ms |
28652 KB |
Output is correct |
6 |
Correct |
103 ms |
28140 KB |
Output is correct |
7 |
Correct |
101 ms |
28140 KB |
Output is correct |
8 |
Correct |
118 ms |
28200 KB |
Output is correct |
9 |
Correct |
77 ms |
27044 KB |
Output is correct |
10 |
Correct |
118 ms |
28460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Correct |
16 ms |
23788 KB |
Output is correct |
3 |
Correct |
17 ms |
23916 KB |
Output is correct |
4 |
Correct |
17 ms |
24044 KB |
Output is correct |
5 |
Correct |
17 ms |
23916 KB |
Output is correct |
6 |
Correct |
17 ms |
23916 KB |
Output is correct |
7 |
Correct |
19 ms |
23916 KB |
Output is correct |
8 |
Correct |
17 ms |
23916 KB |
Output is correct |
9 |
Correct |
17 ms |
23916 KB |
Output is correct |
10 |
Correct |
17 ms |
23916 KB |
Output is correct |
11 |
Correct |
19 ms |
24044 KB |
Output is correct |
12 |
Correct |
20 ms |
24172 KB |
Output is correct |
13 |
Correct |
22 ms |
24204 KB |
Output is correct |
14 |
Correct |
23 ms |
24300 KB |
Output is correct |
15 |
Correct |
23 ms |
24300 KB |
Output is correct |
16 |
Correct |
21 ms |
24172 KB |
Output is correct |
17 |
Correct |
20 ms |
24172 KB |
Output is correct |
18 |
Correct |
21 ms |
24172 KB |
Output is correct |
19 |
Correct |
305 ms |
37996 KB |
Output is correct |
20 |
Correct |
305 ms |
37868 KB |
Output is correct |
21 |
Correct |
288 ms |
37100 KB |
Output is correct |
22 |
Correct |
275 ms |
37228 KB |
Output is correct |
23 |
Correct |
271 ms |
37100 KB |
Output is correct |
24 |
Correct |
227 ms |
35308 KB |
Output is correct |
25 |
Correct |
223 ms |
35308 KB |
Output is correct |
26 |
Correct |
252 ms |
35692 KB |
Output is correct |
27 |
Correct |
247 ms |
35820 KB |
Output is correct |
28 |
Correct |
265 ms |
35972 KB |
Output is correct |
29 |
Correct |
265 ms |
36040 KB |
Output is correct |
30 |
Correct |
266 ms |
36204 KB |
Output is correct |
31 |
Correct |
274 ms |
36204 KB |
Output is correct |
32 |
Correct |
266 ms |
36268 KB |
Output is correct |
33 |
Correct |
261 ms |
36076 KB |
Output is correct |
34 |
Correct |
211 ms |
35036 KB |
Output is correct |
35 |
Correct |
212 ms |
34796 KB |
Output is correct |
36 |
Correct |
205 ms |
34796 KB |
Output is correct |
37 |
Correct |
205 ms |
34796 KB |
Output is correct |
38 |
Correct |
213 ms |
34916 KB |
Output is correct |
39 |
Correct |
241 ms |
34852 KB |
Output is correct |
40 |
Correct |
219 ms |
33056 KB |
Output is correct |
41 |
Correct |
258 ms |
34084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Correct |
16 ms |
23788 KB |
Output is correct |
3 |
Correct |
17 ms |
23916 KB |
Output is correct |
4 |
Correct |
17 ms |
24044 KB |
Output is correct |
5 |
Correct |
17 ms |
23916 KB |
Output is correct |
6 |
Correct |
17 ms |
23916 KB |
Output is correct |
7 |
Correct |
19 ms |
23916 KB |
Output is correct |
8 |
Correct |
17 ms |
23916 KB |
Output is correct |
9 |
Correct |
17 ms |
23916 KB |
Output is correct |
10 |
Correct |
17 ms |
23916 KB |
Output is correct |
11 |
Correct |
19 ms |
24044 KB |
Output is correct |
12 |
Correct |
20 ms |
24172 KB |
Output is correct |
13 |
Correct |
22 ms |
24204 KB |
Output is correct |
14 |
Correct |
23 ms |
24300 KB |
Output is correct |
15 |
Correct |
23 ms |
24300 KB |
Output is correct |
16 |
Correct |
21 ms |
24172 KB |
Output is correct |
17 |
Correct |
20 ms |
24172 KB |
Output is correct |
18 |
Correct |
21 ms |
24172 KB |
Output is correct |
19 |
Correct |
1707 ms |
60848 KB |
Output is correct |
20 |
Correct |
1729 ms |
75228 KB |
Output is correct |
21 |
Correct |
1729 ms |
75084 KB |
Output is correct |
22 |
Correct |
1702 ms |
74980 KB |
Output is correct |
23 |
Correct |
1398 ms |
66796 KB |
Output is correct |
24 |
Correct |
136 ms |
27500 KB |
Output is correct |
25 |
Correct |
130 ms |
29292 KB |
Output is correct |
26 |
Correct |
116 ms |
28524 KB |
Output is correct |
27 |
Correct |
122 ms |
28780 KB |
Output is correct |
28 |
Correct |
119 ms |
28652 KB |
Output is correct |
29 |
Correct |
103 ms |
28140 KB |
Output is correct |
30 |
Correct |
101 ms |
28140 KB |
Output is correct |
31 |
Correct |
118 ms |
28200 KB |
Output is correct |
32 |
Correct |
77 ms |
27044 KB |
Output is correct |
33 |
Correct |
118 ms |
28460 KB |
Output is correct |
34 |
Correct |
305 ms |
37996 KB |
Output is correct |
35 |
Correct |
305 ms |
37868 KB |
Output is correct |
36 |
Correct |
288 ms |
37100 KB |
Output is correct |
37 |
Correct |
275 ms |
37228 KB |
Output is correct |
38 |
Correct |
271 ms |
37100 KB |
Output is correct |
39 |
Correct |
227 ms |
35308 KB |
Output is correct |
40 |
Correct |
223 ms |
35308 KB |
Output is correct |
41 |
Correct |
252 ms |
35692 KB |
Output is correct |
42 |
Correct |
247 ms |
35820 KB |
Output is correct |
43 |
Correct |
265 ms |
35972 KB |
Output is correct |
44 |
Correct |
265 ms |
36040 KB |
Output is correct |
45 |
Correct |
266 ms |
36204 KB |
Output is correct |
46 |
Correct |
274 ms |
36204 KB |
Output is correct |
47 |
Correct |
266 ms |
36268 KB |
Output is correct |
48 |
Correct |
261 ms |
36076 KB |
Output is correct |
49 |
Correct |
211 ms |
35036 KB |
Output is correct |
50 |
Correct |
212 ms |
34796 KB |
Output is correct |
51 |
Correct |
205 ms |
34796 KB |
Output is correct |
52 |
Correct |
205 ms |
34796 KB |
Output is correct |
53 |
Correct |
213 ms |
34916 KB |
Output is correct |
54 |
Correct |
241 ms |
34852 KB |
Output is correct |
55 |
Correct |
219 ms |
33056 KB |
Output is correct |
56 |
Correct |
258 ms |
34084 KB |
Output is correct |
57 |
Correct |
1739 ms |
93828 KB |
Output is correct |
58 |
Correct |
1753 ms |
93840 KB |
Output is correct |
59 |
Correct |
1701 ms |
92292 KB |
Output is correct |
60 |
Correct |
1635 ms |
92780 KB |
Output is correct |
61 |
Correct |
1626 ms |
92404 KB |
Output is correct |
62 |
Correct |
1640 ms |
92212 KB |
Output is correct |
63 |
Correct |
1074 ms |
80876 KB |
Output is correct |
64 |
Correct |
1094 ms |
80804 KB |
Output is correct |
65 |
Correct |
1382 ms |
83948 KB |
Output is correct |
66 |
Correct |
1377 ms |
84084 KB |
Output is correct |
67 |
Correct |
1390 ms |
83968 KB |
Output is correct |
68 |
Correct |
1461 ms |
85848 KB |
Output is correct |
69 |
Correct |
1464 ms |
85772 KB |
Output is correct |
70 |
Correct |
1426 ms |
85316 KB |
Output is correct |
71 |
Correct |
1431 ms |
85456 KB |
Output is correct |
72 |
Correct |
1424 ms |
85452 KB |
Output is correct |
73 |
Correct |
949 ms |
76992 KB |
Output is correct |
74 |
Correct |
980 ms |
77644 KB |
Output is correct |
75 |
Correct |
967 ms |
76788 KB |
Output is correct |
76 |
Correct |
940 ms |
76928 KB |
Output is correct |
77 |
Correct |
980 ms |
76732 KB |
Output is correct |
78 |
Correct |
1294 ms |
80648 KB |
Output is correct |
79 |
Correct |
1008 ms |
68972 KB |
Output is correct |
80 |
Correct |
1278 ms |
74968 KB |
Output is correct |