#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
struct segment_tree{
vector<int> st;
segment_tree(int n) : st(n << 2) {}
void update(int id, int l, int r, int u, int v, int val){
st[id] = max(st[id], val);
if(u <= l && r <= v) return;
int mid = l + r >> 1;
if(u <= mid) update(id << 1, l, mid, u, v, val);
if(mid < v) update(id << 1 | 1, mid + 1, r, u, v, val);
}
int query(int id, int l, int r, int u, int v){
if(v < l || u > r) return 0;
if(u <= l && r <= v) return st[id];
int mid = l + r >> 1;
return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<int> a(N);
for(int i = 0; i < N; ++i){
cin >> a[i];
}
vector<vector<tuple<int, int, int>>> sweep(N);
for(int i = 0; i < M; ++i){
int l, r, k;
cin >> l >> r >> k;
--l, --r;
sweep[r].emplace_back(l, k, i);
}
vector<bool> answer(M, false);
segment_tree tree(N);
stack<int> st;
for(int i = 0; i < N; ++i){
while(!st.empty() && a[st.top()] <= a[i]) st.pop();
if(!st.empty()) tree.update(1, 0, N - 1, st.top(), i, a[st.top()] + a[i]);
for(auto [j, k, id] : sweep[i]){
answer[id] = (tree.query(1, 0, N - 1, j, i) <= k);
}
st.push(i);
}
for(auto it : answer) cout << it << '\n';
return 0;
}
Compilation message
sortbooks.cpp: In member function 'void segment_tree::update(int, int, int, int, int, int)':
sortbooks.cpp:14:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
14 | int mid = l + r >> 1;
| ~~^~~
sortbooks.cpp: In member function 'int segment_tree::query(int, int, int, int, int)':
sortbooks.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
22 | int mid = l + r >> 1;
| ~~^~~
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:55:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
55 | for(auto [j, k, id] : sweep[i]){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
913 ms |
83044 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
67 ms |
7732 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |