#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld; // typedef double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<ld> vd;
typedef vector<vd> vvd;
typedef complex<ld> cd;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef string str;
#define int ll
template<class A, class B>
inline bool mmin(A& a, B b) {
if (b < a) {
a = b;
return 1;
}
return 0;
}
template<class A, class B>
inline bool mmax(A& a, B b) {
if (b > a) {
a = b;
return 1;
}
return 0;
}
ld nxt_ld() {
string s;
cin >> s;
return stold(s);
}
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ef emplace_front
#define ppb pop_back
#define ppf pop_front
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
const int N = 1e6 + 15, NN = 1e6 + 10;
int t[4 * N];
void upd(int v, int l, int r, int i, int x) {
if (r - l == 1) mmax(t[v], x); else {
int m = (l + r) / 2;
if (i < m) upd(2 * v, l, m, i, x); else upd(2 * v + 1, m, r, i, x);
t[v] = max(t[2 * v], t[2 * v + 1]);
}
}
int get(int v, int tl, int tr, int l, int r) {
if (tl >= r || tr <= l) return 0;
if (tl >= l && tr <= r) return t[v];
int tm = (tl + tr) / 2;
return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm, tr, l, r));
}
signed main() {
/*freopen("cbarn.in", "r", stdin);
freopen("cbran.out", "w", stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vi w(n);
for (int i = 0; i < n; i++) cin >> w[i];
vi go(n, -1), st;
for (int i = n - 1; i >= 0; i--) {
while (!st.empty() && w[i] > w[st.back()]) {
go[st.back()] = i;
st.pop_back();
}
st.pb(i);
}
vi num(n);
for (int i = 0; i < n; i++) num[i] = go[i] == -1 ? 0 : w[i] + w[go[i]];
vi l(m), r(m), k(m);
vvi atr(n + 1);
vi ans(m, 1);
for (int i = 0; i < m; i++) {
cin >> l[i] >> r[i] >> k[i];
l[i]--;
atr[r[i]].pb(i);
}
for (int i = 0; i <= n; i++) {
for (auto j : atr[i]) {
if (get(1, 0, N, l[j] + 1, N) > k[j]) ans[j] = 0;
}
if (i != n) upd(1, 0, N, go[i] + 1, num[i]);
}
for (auto x : ans) cout << x << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
7 ms |
512 KB |
Output is correct |
12 |
Correct |
8 ms |
768 KB |
Output is correct |
13 |
Correct |
8 ms |
768 KB |
Output is correct |
14 |
Correct |
10 ms |
896 KB |
Output is correct |
15 |
Correct |
10 ms |
896 KB |
Output is correct |
16 |
Correct |
9 ms |
768 KB |
Output is correct |
17 |
Correct |
8 ms |
768 KB |
Output is correct |
18 |
Correct |
9 ms |
768 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1665 ms |
87692 KB |
Output is correct |
2 |
Correct |
1673 ms |
120568 KB |
Output is correct |
3 |
Correct |
1682 ms |
120420 KB |
Output is correct |
4 |
Correct |
1715 ms |
120664 KB |
Output is correct |
5 |
Correct |
1462 ms |
108132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
8952 KB |
Output is correct |
2 |
Correct |
107 ms |
10224 KB |
Output is correct |
3 |
Correct |
97 ms |
9460 KB |
Output is correct |
4 |
Correct |
122 ms |
9612 KB |
Output is correct |
5 |
Correct |
101 ms |
9844 KB |
Output is correct |
6 |
Correct |
86 ms |
8568 KB |
Output is correct |
7 |
Correct |
86 ms |
8560 KB |
Output is correct |
8 |
Correct |
96 ms |
9076 KB |
Output is correct |
9 |
Correct |
55 ms |
3956 KB |
Output is correct |
10 |
Correct |
93 ms |
9216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
7 ms |
512 KB |
Output is correct |
12 |
Correct |
8 ms |
768 KB |
Output is correct |
13 |
Correct |
8 ms |
768 KB |
Output is correct |
14 |
Correct |
10 ms |
896 KB |
Output is correct |
15 |
Correct |
10 ms |
896 KB |
Output is correct |
16 |
Correct |
9 ms |
768 KB |
Output is correct |
17 |
Correct |
8 ms |
768 KB |
Output is correct |
18 |
Correct |
9 ms |
768 KB |
Output is correct |
19 |
Correct |
268 ms |
22008 KB |
Output is correct |
20 |
Correct |
276 ms |
24156 KB |
Output is correct |
21 |
Correct |
219 ms |
22264 KB |
Output is correct |
22 |
Correct |
214 ms |
22392 KB |
Output is correct |
23 |
Correct |
221 ms |
22268 KB |
Output is correct |
24 |
Correct |
200 ms |
19440 KB |
Output is correct |
25 |
Correct |
195 ms |
19568 KB |
Output is correct |
26 |
Correct |
206 ms |
20336 KB |
Output is correct |
27 |
Correct |
217 ms |
20336 KB |
Output is correct |
28 |
Correct |
215 ms |
20720 KB |
Output is correct |
29 |
Correct |
236 ms |
21744 KB |
Output is correct |
30 |
Correct |
228 ms |
21744 KB |
Output is correct |
31 |
Correct |
232 ms |
21488 KB |
Output is correct |
32 |
Correct |
231 ms |
21616 KB |
Output is correct |
33 |
Correct |
244 ms |
21616 KB |
Output is correct |
34 |
Correct |
184 ms |
19184 KB |
Output is correct |
35 |
Correct |
189 ms |
19184 KB |
Output is correct |
36 |
Correct |
185 ms |
19060 KB |
Output is correct |
37 |
Correct |
190 ms |
18928 KB |
Output is correct |
38 |
Correct |
183 ms |
19184 KB |
Output is correct |
39 |
Correct |
219 ms |
20848 KB |
Output is correct |
40 |
Correct |
183 ms |
16116 KB |
Output is correct |
41 |
Correct |
201 ms |
19316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
5 ms |
384 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
5 ms |
384 KB |
Output is correct |
11 |
Correct |
7 ms |
512 KB |
Output is correct |
12 |
Correct |
8 ms |
768 KB |
Output is correct |
13 |
Correct |
8 ms |
768 KB |
Output is correct |
14 |
Correct |
10 ms |
896 KB |
Output is correct |
15 |
Correct |
10 ms |
896 KB |
Output is correct |
16 |
Correct |
9 ms |
768 KB |
Output is correct |
17 |
Correct |
8 ms |
768 KB |
Output is correct |
18 |
Correct |
9 ms |
768 KB |
Output is correct |
19 |
Correct |
1665 ms |
87692 KB |
Output is correct |
20 |
Correct |
1673 ms |
120568 KB |
Output is correct |
21 |
Correct |
1682 ms |
120420 KB |
Output is correct |
22 |
Correct |
1715 ms |
120664 KB |
Output is correct |
23 |
Correct |
1462 ms |
108132 KB |
Output is correct |
24 |
Correct |
107 ms |
8952 KB |
Output is correct |
25 |
Correct |
107 ms |
10224 KB |
Output is correct |
26 |
Correct |
97 ms |
9460 KB |
Output is correct |
27 |
Correct |
122 ms |
9612 KB |
Output is correct |
28 |
Correct |
101 ms |
9844 KB |
Output is correct |
29 |
Correct |
86 ms |
8568 KB |
Output is correct |
30 |
Correct |
86 ms |
8560 KB |
Output is correct |
31 |
Correct |
96 ms |
9076 KB |
Output is correct |
32 |
Correct |
55 ms |
3956 KB |
Output is correct |
33 |
Correct |
93 ms |
9216 KB |
Output is correct |
34 |
Correct |
268 ms |
22008 KB |
Output is correct |
35 |
Correct |
276 ms |
24156 KB |
Output is correct |
36 |
Correct |
219 ms |
22264 KB |
Output is correct |
37 |
Correct |
214 ms |
22392 KB |
Output is correct |
38 |
Correct |
221 ms |
22268 KB |
Output is correct |
39 |
Correct |
200 ms |
19440 KB |
Output is correct |
40 |
Correct |
195 ms |
19568 KB |
Output is correct |
41 |
Correct |
206 ms |
20336 KB |
Output is correct |
42 |
Correct |
217 ms |
20336 KB |
Output is correct |
43 |
Correct |
215 ms |
20720 KB |
Output is correct |
44 |
Correct |
236 ms |
21744 KB |
Output is correct |
45 |
Correct |
228 ms |
21744 KB |
Output is correct |
46 |
Correct |
232 ms |
21488 KB |
Output is correct |
47 |
Correct |
231 ms |
21616 KB |
Output is correct |
48 |
Correct |
244 ms |
21616 KB |
Output is correct |
49 |
Correct |
184 ms |
19184 KB |
Output is correct |
50 |
Correct |
189 ms |
19184 KB |
Output is correct |
51 |
Correct |
185 ms |
19060 KB |
Output is correct |
52 |
Correct |
190 ms |
18928 KB |
Output is correct |
53 |
Correct |
183 ms |
19184 KB |
Output is correct |
54 |
Correct |
219 ms |
20848 KB |
Output is correct |
55 |
Correct |
183 ms |
16116 KB |
Output is correct |
56 |
Correct |
201 ms |
19316 KB |
Output is correct |
57 |
Correct |
1665 ms |
119432 KB |
Output is correct |
58 |
Correct |
1693 ms |
119528 KB |
Output is correct |
59 |
Correct |
1559 ms |
115448 KB |
Output is correct |
60 |
Correct |
1583 ms |
115448 KB |
Output is correct |
61 |
Correct |
1590 ms |
115376 KB |
Output is correct |
62 |
Correct |
1589 ms |
115404 KB |
Output is correct |
63 |
Correct |
1020 ms |
95048 KB |
Output is correct |
64 |
Correct |
1032 ms |
95072 KB |
Output is correct |
65 |
Correct |
1355 ms |
102240 KB |
Output is correct |
66 |
Correct |
1396 ms |
102196 KB |
Output is correct |
67 |
Correct |
1387 ms |
102696 KB |
Output is correct |
68 |
Correct |
1457 ms |
107048 KB |
Output is correct |
69 |
Correct |
1493 ms |
107164 KB |
Output is correct |
70 |
Correct |
1460 ms |
106364 KB |
Output is correct |
71 |
Correct |
1461 ms |
106292 KB |
Output is correct |
72 |
Correct |
1439 ms |
106468 KB |
Output is correct |
73 |
Correct |
1020 ms |
93060 KB |
Output is correct |
74 |
Correct |
1042 ms |
94056 KB |
Output is correct |
75 |
Correct |
1006 ms |
93024 KB |
Output is correct |
76 |
Correct |
1028 ms |
93284 KB |
Output is correct |
77 |
Correct |
1043 ms |
93068 KB |
Output is correct |
78 |
Correct |
1384 ms |
103276 KB |
Output is correct |
79 |
Correct |
1022 ms |
72860 KB |
Output is correct |
80 |
Correct |
1239 ms |
94976 KB |
Output is correct |