#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
const ll inf=1e15;
#define pb push_back
const int INF=(0x3f3f3f3f);
int a[N],b[N];
int T[4*N],mx[4*N];
void build(int v,int tl,int tr){
if(tl==tr){
T[v]=b[tl];
return;
}
int tm=(tl+tr)/2;
build(v+v,tl,tm);
build(v+v+1,tm+1,tr);
T[v]=max(T[v+v],T[v+v+1]);
}
int l[N],r[N],mo[N],answ[N];
vector<int>idx[N];
vector<int>st[N];
int query(int v,int tl,int tr,int l,int r){
if(l>r)return 0;
if(tl==l&&tr==r)return T[v];
int tm=(tl+tr)/2;
return max(query(v+v,tl,tm,l,min(tm,r)),query(v+v+1,tm+1,tr,max(tm+1,l),r));
}
void update(int v,int tl,int tr,int pos,int val){
if(tl==tr){
T[v]=val;
return;
}
int tm=(tl+tr)/2;
if(pos<=tm)update(v+v,tl,tm,pos,val);
else update(v+v+1,tm+1,tr,pos,val);
T[v]=max(T[v+v],T[v+v+1]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
vector<int>h;
for(int i=1;i<=n;i++){
cin>>a[i];
while(!h.empty()&&a[h.back()]<=a[i])h.pop_back();
if(h.empty())h.pb(i);
else{
int idx=h.back();
st[idx].pb(i);
b[i]=a[idx]+a[i];
h.pb(i);
}
}
build(1,1,n);
for(int i=1;i<=m;i++){
cin>>l[i]>>r[i]>>mo[i];
idx[l[i]].pb(i);
}
for(int i=1;i<=n;i++){
for(auto x:idx[i]){
answ[x]=query(1,1,n,i,r[x]);
}
for(auto x:st[i]){
update(1,1,n,x,0);
}
}
for(int i=1;i<=m;i++){
cout<<(answ[i]<=mo[i]?"1\n":"0\n");
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
47352 KB |
Output is correct |
2 |
Correct |
44 ms |
47352 KB |
Output is correct |
3 |
Correct |
44 ms |
47352 KB |
Output is correct |
4 |
Correct |
45 ms |
47352 KB |
Output is correct |
5 |
Correct |
45 ms |
47352 KB |
Output is correct |
6 |
Correct |
45 ms |
47480 KB |
Output is correct |
7 |
Correct |
44 ms |
47352 KB |
Output is correct |
8 |
Correct |
45 ms |
47352 KB |
Output is correct |
9 |
Correct |
45 ms |
47480 KB |
Output is correct |
10 |
Correct |
44 ms |
47352 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
47352 KB |
Output is correct |
2 |
Correct |
44 ms |
47352 KB |
Output is correct |
3 |
Correct |
44 ms |
47352 KB |
Output is correct |
4 |
Correct |
45 ms |
47352 KB |
Output is correct |
5 |
Correct |
45 ms |
47352 KB |
Output is correct |
6 |
Correct |
45 ms |
47480 KB |
Output is correct |
7 |
Correct |
44 ms |
47352 KB |
Output is correct |
8 |
Correct |
45 ms |
47352 KB |
Output is correct |
9 |
Correct |
45 ms |
47480 KB |
Output is correct |
10 |
Correct |
44 ms |
47352 KB |
Output is correct |
11 |
Correct |
47 ms |
47556 KB |
Output is correct |
12 |
Correct |
49 ms |
47736 KB |
Output is correct |
13 |
Correct |
48 ms |
47736 KB |
Output is correct |
14 |
Correct |
51 ms |
47868 KB |
Output is correct |
15 |
Correct |
50 ms |
47968 KB |
Output is correct |
16 |
Correct |
49 ms |
47736 KB |
Output is correct |
17 |
Correct |
49 ms |
47736 KB |
Output is correct |
18 |
Correct |
49 ms |
47736 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1937 ms |
115160 KB |
Output is correct |
2 |
Correct |
1968 ms |
137412 KB |
Output is correct |
3 |
Correct |
1975 ms |
145044 KB |
Output is correct |
4 |
Correct |
2037 ms |
147616 KB |
Output is correct |
5 |
Correct |
1673 ms |
128004 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
181 ms |
55908 KB |
Output is correct |
2 |
Correct |
161 ms |
55344 KB |
Output is correct |
3 |
Correct |
155 ms |
54060 KB |
Output is correct |
4 |
Correct |
153 ms |
54296 KB |
Output is correct |
5 |
Correct |
153 ms |
54236 KB |
Output is correct |
6 |
Correct |
121 ms |
53116 KB |
Output is correct |
7 |
Correct |
122 ms |
53052 KB |
Output is correct |
8 |
Correct |
141 ms |
54028 KB |
Output is correct |
9 |
Correct |
87 ms |
51060 KB |
Output is correct |
10 |
Correct |
137 ms |
53952 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
47352 KB |
Output is correct |
2 |
Correct |
44 ms |
47352 KB |
Output is correct |
3 |
Correct |
44 ms |
47352 KB |
Output is correct |
4 |
Correct |
45 ms |
47352 KB |
Output is correct |
5 |
Correct |
45 ms |
47352 KB |
Output is correct |
6 |
Correct |
45 ms |
47480 KB |
Output is correct |
7 |
Correct |
44 ms |
47352 KB |
Output is correct |
8 |
Correct |
45 ms |
47352 KB |
Output is correct |
9 |
Correct |
45 ms |
47480 KB |
Output is correct |
10 |
Correct |
44 ms |
47352 KB |
Output is correct |
11 |
Correct |
47 ms |
47556 KB |
Output is correct |
12 |
Correct |
49 ms |
47736 KB |
Output is correct |
13 |
Correct |
48 ms |
47736 KB |
Output is correct |
14 |
Correct |
51 ms |
47868 KB |
Output is correct |
15 |
Correct |
50 ms |
47968 KB |
Output is correct |
16 |
Correct |
49 ms |
47736 KB |
Output is correct |
17 |
Correct |
49 ms |
47736 KB |
Output is correct |
18 |
Correct |
49 ms |
47736 KB |
Output is correct |
19 |
Correct |
397 ms |
64048 KB |
Output is correct |
20 |
Correct |
372 ms |
64248 KB |
Output is correct |
21 |
Correct |
313 ms |
61916 KB |
Output is correct |
22 |
Correct |
322 ms |
61816 KB |
Output is correct |
23 |
Correct |
314 ms |
62072 KB |
Output is correct |
24 |
Correct |
246 ms |
56568 KB |
Output is correct |
25 |
Correct |
248 ms |
58024 KB |
Output is correct |
26 |
Correct |
297 ms |
58308 KB |
Output is correct |
27 |
Correct |
292 ms |
57484 KB |
Output is correct |
28 |
Correct |
290 ms |
57940 KB |
Output is correct |
29 |
Correct |
312 ms |
59128 KB |
Output is correct |
30 |
Correct |
322 ms |
59128 KB |
Output is correct |
31 |
Correct |
317 ms |
59032 KB |
Output is correct |
32 |
Correct |
318 ms |
59128 KB |
Output is correct |
33 |
Correct |
321 ms |
59000 KB |
Output is correct |
34 |
Correct |
228 ms |
56316 KB |
Output is correct |
35 |
Correct |
232 ms |
56324 KB |
Output is correct |
36 |
Correct |
227 ms |
56116 KB |
Output is correct |
37 |
Correct |
226 ms |
56208 KB |
Output is correct |
38 |
Correct |
228 ms |
56184 KB |
Output is correct |
39 |
Correct |
301 ms |
60656 KB |
Output is correct |
40 |
Correct |
222 ms |
58352 KB |
Output is correct |
41 |
Correct |
263 ms |
61064 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
47352 KB |
Output is correct |
2 |
Correct |
44 ms |
47352 KB |
Output is correct |
3 |
Correct |
44 ms |
47352 KB |
Output is correct |
4 |
Correct |
45 ms |
47352 KB |
Output is correct |
5 |
Correct |
45 ms |
47352 KB |
Output is correct |
6 |
Correct |
45 ms |
47480 KB |
Output is correct |
7 |
Correct |
44 ms |
47352 KB |
Output is correct |
8 |
Correct |
45 ms |
47352 KB |
Output is correct |
9 |
Correct |
45 ms |
47480 KB |
Output is correct |
10 |
Correct |
44 ms |
47352 KB |
Output is correct |
11 |
Correct |
47 ms |
47556 KB |
Output is correct |
12 |
Correct |
49 ms |
47736 KB |
Output is correct |
13 |
Correct |
48 ms |
47736 KB |
Output is correct |
14 |
Correct |
51 ms |
47868 KB |
Output is correct |
15 |
Correct |
50 ms |
47968 KB |
Output is correct |
16 |
Correct |
49 ms |
47736 KB |
Output is correct |
17 |
Correct |
49 ms |
47736 KB |
Output is correct |
18 |
Correct |
49 ms |
47736 KB |
Output is correct |
19 |
Correct |
1937 ms |
115160 KB |
Output is correct |
20 |
Correct |
1968 ms |
137412 KB |
Output is correct |
21 |
Correct |
1975 ms |
145044 KB |
Output is correct |
22 |
Correct |
2037 ms |
147616 KB |
Output is correct |
23 |
Correct |
1673 ms |
128004 KB |
Output is correct |
24 |
Correct |
181 ms |
55908 KB |
Output is correct |
25 |
Correct |
161 ms |
55344 KB |
Output is correct |
26 |
Correct |
155 ms |
54060 KB |
Output is correct |
27 |
Correct |
153 ms |
54296 KB |
Output is correct |
28 |
Correct |
153 ms |
54236 KB |
Output is correct |
29 |
Correct |
121 ms |
53116 KB |
Output is correct |
30 |
Correct |
122 ms |
53052 KB |
Output is correct |
31 |
Correct |
141 ms |
54028 KB |
Output is correct |
32 |
Correct |
87 ms |
51060 KB |
Output is correct |
33 |
Correct |
137 ms |
53952 KB |
Output is correct |
34 |
Correct |
397 ms |
64048 KB |
Output is correct |
35 |
Correct |
372 ms |
64248 KB |
Output is correct |
36 |
Correct |
313 ms |
61916 KB |
Output is correct |
37 |
Correct |
322 ms |
61816 KB |
Output is correct |
38 |
Correct |
314 ms |
62072 KB |
Output is correct |
39 |
Correct |
246 ms |
56568 KB |
Output is correct |
40 |
Correct |
248 ms |
58024 KB |
Output is correct |
41 |
Correct |
297 ms |
58308 KB |
Output is correct |
42 |
Correct |
292 ms |
57484 KB |
Output is correct |
43 |
Correct |
290 ms |
57940 KB |
Output is correct |
44 |
Correct |
312 ms |
59128 KB |
Output is correct |
45 |
Correct |
322 ms |
59128 KB |
Output is correct |
46 |
Correct |
317 ms |
59032 KB |
Output is correct |
47 |
Correct |
318 ms |
59128 KB |
Output is correct |
48 |
Correct |
321 ms |
59000 KB |
Output is correct |
49 |
Correct |
228 ms |
56316 KB |
Output is correct |
50 |
Correct |
232 ms |
56324 KB |
Output is correct |
51 |
Correct |
227 ms |
56116 KB |
Output is correct |
52 |
Correct |
226 ms |
56208 KB |
Output is correct |
53 |
Correct |
228 ms |
56184 KB |
Output is correct |
54 |
Correct |
301 ms |
60656 KB |
Output is correct |
55 |
Correct |
222 ms |
58352 KB |
Output is correct |
56 |
Correct |
263 ms |
61064 KB |
Output is correct |
57 |
Correct |
2021 ms |
150704 KB |
Output is correct |
58 |
Correct |
1992 ms |
150580 KB |
Output is correct |
59 |
Correct |
1886 ms |
114364 KB |
Output is correct |
60 |
Correct |
1889 ms |
125304 KB |
Output is correct |
61 |
Correct |
1932 ms |
143604 KB |
Output is correct |
62 |
Correct |
1902 ms |
133752 KB |
Output is correct |
63 |
Correct |
1165 ms |
92896 KB |
Output is correct |
64 |
Correct |
1165 ms |
89244 KB |
Output is correct |
65 |
Correct |
1583 ms |
114996 KB |
Output is correct |
66 |
Correct |
1562 ms |
121700 KB |
Output is correct |
67 |
Correct |
1591 ms |
124576 KB |
Output is correct |
68 |
Correct |
1700 ms |
130436 KB |
Output is correct |
69 |
Correct |
1675 ms |
127192 KB |
Output is correct |
70 |
Correct |
1670 ms |
128328 KB |
Output is correct |
71 |
Correct |
1670 ms |
128204 KB |
Output is correct |
72 |
Correct |
1651 ms |
128364 KB |
Output is correct |
73 |
Correct |
1086 ms |
112888 KB |
Output is correct |
74 |
Correct |
1126 ms |
112972 KB |
Output is correct |
75 |
Correct |
1076 ms |
112536 KB |
Output is correct |
76 |
Correct |
1070 ms |
111852 KB |
Output is correct |
77 |
Correct |
1078 ms |
111880 KB |
Output is correct |
78 |
Correct |
1448 ms |
122644 KB |
Output is correct |
79 |
Correct |
1000 ms |
105180 KB |
Output is correct |
80 |
Correct |
1388 ms |
119288 KB |
Output is correct |