#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=1e6+5;
const int inf = 2e9 + 10;
int n, m;
int a[mxn] = {};
struct segtree {
int tree[4*mxn];
void update(int node,int b,int e, int p, int v) {
if(b > p || e < p) return;
if(b == e) {
tree[node] = v;
return;
}
int mid = b + e >> 1;
int left = node << 1;
int right = left | 1;
update(left, b, mid, p, v);
update(right, mid + 1, e, p, v);
tree[node] = max(tree[left], tree[right]);
}
int query(int node,int b,int e,int l,int r) {
if(e<l || b>r) return 0;
if(b >= l && e <= r) return tree[node];
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
return max(query(left, b, mid, l, r), query(right, mid + 1, e, l, r));
}
} st;
struct BIT
{
int bit[mxn] = {};
void update(int p,int v) {
if(p==0) return;
for(;p<mxn;p+=p&-p) bit[p] += v;
}
int query(int p) {
int r = 0;
for(;p > 0; p -= p&-p) r += bit[p];
return r;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
} bt, dn;
int main() {
cin >> n >> m;
vector<pii> b;
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b.emplace_back(a[i], i);
}
a[0] = inf;
stack<int> St;
St.push(0);
int nxt[n + 5];
vector<int> con[n + 5];
for(int i = 1; i <= n; i++) {
while(a[St.top()] < a[i]) St.pop();
con[St.top()].push_back(i);
if(St.top() != 0) st.update(1, 1, n, i, a[St.top()] + a[i]);
St.push(i);
}
vector< tuple<int,int, int> > query[n + 1];
for(int i = 1; i <= m; i++) {
int l, r, k;
scanf("%d%d%d", &l, &r, &k);
query[l].emplace_back(r, i, k);
}
bool res[m + 1];
for(int l = 1; l <= n; l++) {
for(auto [r, i, k] : query[l]) {
int v = st.query(1, 1, n, l, r);
res[i] = (v <= k);
}
for(int x : con[l]) {
st.update(1, 1, n, x, 0);
}
}
for(int i = 1; i <= m; i++) {
printf("%d\n", res[i]);
}
}
Compilation message
selling_rna.cpp: In member function 'void segtree::update(int, int, int, int, int)':
selling_rna.cpp:19:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
19 | int mid = b + e >> 1;
| ~~^~~
selling_rna.cpp: In member function 'int segtree::query(int, int, int, int, int)':
selling_rna.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
29 | int mid=b+e>>1;
| ~^~
selling_rna.cpp: In function 'int main()':
selling_rna.cpp:68:9: warning: unused variable 'nxt' [-Wunused-variable]
68 | int nxt[n + 5];
| ^~~
selling_rna.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
59 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
selling_rna.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%d%d%d", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
588 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
6508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
