#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int n, q;
const int N=1e6;
int mx[4*N], lazy[4*N];
int a[N];
void push(int x, int lx, int rx){
if(rx-lx==1 || !lazy[x]) return;
for(int y:{2*x+1, 2*x+2}){
mx[y]+=lazy[x];
lazy[y]+=lazy[x];
}
lazy[x]=0;
}
void add(int l, int r, int v, int x, int lx, int rx){
push(x,lx,rx);
if(lx>=r || rx<=l) return;
if(lx>=l && rx<=r){
lazy[x]+=v;
mx[x]+=v;
return;
}
int m=(lx+rx)/2;
add(l,r,v,2*x+1,lx,m);
add(l,r,v,2*x+2,m,rx);
mx[x]=max(mx[2*x+1], mx[2*x+2]);
}
void add(int l, int r, int v){
if(r<=l) return;
add(l, r, v, 0, 0, n);
}
int get_mx(int l, int r, int x, int lx, int rx){
push(x,lx,rx);
if(lx>=r || rx<=l) return -1;
if(lx>=l && rx<=r){
return mx[x];
}
int m=(lx+rx)/2;
return max(get_mx(l,r,2*x+1,lx,m), get_mx(l,r,2*x+2,m,rx));
}
int get_mx(int l, int r){
return get_mx(l,r,0,0,n);
}
void build(int x, int lx, int rx){
if(rx-lx==1){
mx[x]=a[lx];
return;
}
int m=(lx+rx)/2;
build(2*x+1, lx, m);
build(2*x+2, m, rx);
mx[x]=max(mx[2*x+1], mx[2*x+2]);
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
for(int i=0; i<n; i++){
cin >> a[i];
}
build(0, 0, n);
vector<vector<int>> qu(n), lr(q, vector<int>(2));
vector<int> ans(q), k(q);
for(int i=0; i<q; i++){
cin >> lr[i][0] >> lr[i][1] >> k[i];
lr[i][0]--, lr[i][1]--;
qu[lr[i][0]].push_back(i);
}
stack<int> s;
s.push(n);
int inf=2e9;
for(int i=n-1; i>=0; i--){
while(s.size()>1 && a[i]>a[s.top()]){
int j=s.top(); s.pop();
int j2=s.top();
add(j+1, j2, -a[j]);
add(j,j+1,inf);
}
add(i,i+1,-inf);
add(i+1,s.top(),a[i]);
s.push(i);
// for(int j=0; j<n; j++){
// cout << get_mx(j,j+1) << " ";
// }
// cout << '\n';
for(int p:qu[i]){
// cout << "ans " << p << " " << get_mx(i,lr[p][1]+1) << "\n";
ans[p]=get_mx(i,lr[p][1]+1);
}
}
for(int i=0; i<q; i++){
cout << (k[i]>=ans[i]) << "\n";
}
}
// range add
// range max
// tuck a knife with my heart up my sleeve
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
5 ms |
852 KB |
Output is correct |
13 |
Correct |
6 ms |
852 KB |
Output is correct |
14 |
Correct |
7 ms |
1108 KB |
Output is correct |
15 |
Correct |
7 ms |
1060 KB |
Output is correct |
16 |
Correct |
6 ms |
1008 KB |
Output is correct |
17 |
Correct |
4 ms |
980 KB |
Output is correct |
18 |
Correct |
6 ms |
1052 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2372 ms |
126664 KB |
Output is correct |
2 |
Correct |
2344 ms |
159680 KB |
Output is correct |
3 |
Correct |
2302 ms |
159560 KB |
Output is correct |
4 |
Correct |
2307 ms |
159616 KB |
Output is correct |
5 |
Correct |
1767 ms |
161772 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
196 ms |
13572 KB |
Output is correct |
2 |
Correct |
156 ms |
14408 KB |
Output is correct |
3 |
Correct |
116 ms |
15308 KB |
Output is correct |
4 |
Correct |
118 ms |
15556 KB |
Output is correct |
5 |
Correct |
131 ms |
15704 KB |
Output is correct |
6 |
Correct |
107 ms |
14088 KB |
Output is correct |
7 |
Correct |
105 ms |
14088 KB |
Output is correct |
8 |
Correct |
124 ms |
14596 KB |
Output is correct |
9 |
Correct |
54 ms |
8588 KB |
Output is correct |
10 |
Correct |
118 ms |
14864 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
5 ms |
852 KB |
Output is correct |
13 |
Correct |
6 ms |
852 KB |
Output is correct |
14 |
Correct |
7 ms |
1108 KB |
Output is correct |
15 |
Correct |
7 ms |
1060 KB |
Output is correct |
16 |
Correct |
6 ms |
1008 KB |
Output is correct |
17 |
Correct |
4 ms |
980 KB |
Output is correct |
18 |
Correct |
6 ms |
1052 KB |
Output is correct |
19 |
Correct |
381 ms |
33348 KB |
Output is correct |
20 |
Correct |
386 ms |
33356 KB |
Output is correct |
21 |
Correct |
324 ms |
30812 KB |
Output is correct |
22 |
Correct |
335 ms |
30904 KB |
Output is correct |
23 |
Correct |
327 ms |
30924 KB |
Output is correct |
24 |
Correct |
249 ms |
30924 KB |
Output is correct |
25 |
Correct |
238 ms |
30972 KB |
Output is correct |
26 |
Correct |
261 ms |
31996 KB |
Output is correct |
27 |
Correct |
277 ms |
32004 KB |
Output is correct |
28 |
Correct |
299 ms |
32472 KB |
Output is correct |
29 |
Correct |
329 ms |
33664 KB |
Output is correct |
30 |
Correct |
297 ms |
33680 KB |
Output is correct |
31 |
Correct |
316 ms |
33648 KB |
Output is correct |
32 |
Correct |
305 ms |
33560 KB |
Output is correct |
33 |
Correct |
342 ms |
33632 KB |
Output is correct |
34 |
Correct |
248 ms |
30444 KB |
Output is correct |
35 |
Correct |
271 ms |
30416 KB |
Output is correct |
36 |
Correct |
262 ms |
30204 KB |
Output is correct |
37 |
Correct |
287 ms |
30248 KB |
Output is correct |
38 |
Correct |
248 ms |
30448 KB |
Output is correct |
39 |
Correct |
273 ms |
30708 KB |
Output is correct |
40 |
Correct |
212 ms |
25732 KB |
Output is correct |
41 |
Correct |
293 ms |
30208 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
316 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
4 ms |
596 KB |
Output is correct |
12 |
Correct |
5 ms |
852 KB |
Output is correct |
13 |
Correct |
6 ms |
852 KB |
Output is correct |
14 |
Correct |
7 ms |
1108 KB |
Output is correct |
15 |
Correct |
7 ms |
1060 KB |
Output is correct |
16 |
Correct |
6 ms |
1008 KB |
Output is correct |
17 |
Correct |
4 ms |
980 KB |
Output is correct |
18 |
Correct |
6 ms |
1052 KB |
Output is correct |
19 |
Correct |
2372 ms |
126664 KB |
Output is correct |
20 |
Correct |
2344 ms |
159680 KB |
Output is correct |
21 |
Correct |
2302 ms |
159560 KB |
Output is correct |
22 |
Correct |
2307 ms |
159616 KB |
Output is correct |
23 |
Correct |
1767 ms |
161772 KB |
Output is correct |
24 |
Correct |
196 ms |
13572 KB |
Output is correct |
25 |
Correct |
156 ms |
14408 KB |
Output is correct |
26 |
Correct |
116 ms |
15308 KB |
Output is correct |
27 |
Correct |
118 ms |
15556 KB |
Output is correct |
28 |
Correct |
131 ms |
15704 KB |
Output is correct |
29 |
Correct |
107 ms |
14088 KB |
Output is correct |
30 |
Correct |
105 ms |
14088 KB |
Output is correct |
31 |
Correct |
124 ms |
14596 KB |
Output is correct |
32 |
Correct |
54 ms |
8588 KB |
Output is correct |
33 |
Correct |
118 ms |
14864 KB |
Output is correct |
34 |
Correct |
381 ms |
33348 KB |
Output is correct |
35 |
Correct |
386 ms |
33356 KB |
Output is correct |
36 |
Correct |
324 ms |
30812 KB |
Output is correct |
37 |
Correct |
335 ms |
30904 KB |
Output is correct |
38 |
Correct |
327 ms |
30924 KB |
Output is correct |
39 |
Correct |
249 ms |
30924 KB |
Output is correct |
40 |
Correct |
238 ms |
30972 KB |
Output is correct |
41 |
Correct |
261 ms |
31996 KB |
Output is correct |
42 |
Correct |
277 ms |
32004 KB |
Output is correct |
43 |
Correct |
299 ms |
32472 KB |
Output is correct |
44 |
Correct |
329 ms |
33664 KB |
Output is correct |
45 |
Correct |
297 ms |
33680 KB |
Output is correct |
46 |
Correct |
316 ms |
33648 KB |
Output is correct |
47 |
Correct |
305 ms |
33560 KB |
Output is correct |
48 |
Correct |
342 ms |
33632 KB |
Output is correct |
49 |
Correct |
248 ms |
30444 KB |
Output is correct |
50 |
Correct |
271 ms |
30416 KB |
Output is correct |
51 |
Correct |
262 ms |
30204 KB |
Output is correct |
52 |
Correct |
287 ms |
30248 KB |
Output is correct |
53 |
Correct |
248 ms |
30448 KB |
Output is correct |
54 |
Correct |
273 ms |
30708 KB |
Output is correct |
55 |
Correct |
212 ms |
25732 KB |
Output is correct |
56 |
Correct |
293 ms |
30208 KB |
Output is correct |
57 |
Correct |
2314 ms |
162172 KB |
Output is correct |
58 |
Correct |
2568 ms |
162140 KB |
Output is correct |
59 |
Correct |
2685 ms |
156560 KB |
Output is correct |
60 |
Correct |
2228 ms |
156452 KB |
Output is correct |
61 |
Correct |
2159 ms |
156504 KB |
Output is correct |
62 |
Correct |
2214 ms |
156520 KB |
Output is correct |
63 |
Correct |
1310 ms |
148264 KB |
Output is correct |
64 |
Correct |
1309 ms |
148080 KB |
Output is correct |
65 |
Correct |
1614 ms |
157704 KB |
Output is correct |
66 |
Correct |
1634 ms |
157776 KB |
Output is correct |
67 |
Correct |
1642 ms |
158232 KB |
Output is correct |
68 |
Correct |
1756 ms |
164408 KB |
Output is correct |
69 |
Correct |
1762 ms |
164288 KB |
Output is correct |
70 |
Correct |
1740 ms |
163404 KB |
Output is correct |
71 |
Correct |
1800 ms |
163328 KB |
Output is correct |
72 |
Correct |
1886 ms |
163432 KB |
Output is correct |
73 |
Correct |
1533 ms |
145864 KB |
Output is correct |
74 |
Correct |
1358 ms |
146828 KB |
Output is correct |
75 |
Correct |
1402 ms |
145932 KB |
Output is correct |
76 |
Correct |
1304 ms |
145888 KB |
Output is correct |
77 |
Correct |
1341 ms |
146024 KB |
Output is correct |
78 |
Correct |
1979 ms |
150120 KB |
Output is correct |
79 |
Correct |
1070 ms |
120384 KB |
Output is correct |
80 |
Correct |
1618 ms |
147792 KB |
Output is correct |