This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define tii array<int,3>
struct Query {
int l, r, k;
int idx;
bool operator<(const Query &q) {
if (q.r != r) return r < q.r;
return l < q.l;
}
};
struct Segtree {
int n;
vector<int> seg, lz;
Segtree(int sz) {
n=1;
while (n<sz)n*=2;
seg.assign(2*n,-1);
lz.assign(2*n,-1);
}
void pushdown(int x) {
if (lz[x] == -1) return;
if (seg[2*x+1] < lz[x]) {
seg[2*x+1] = lz[2*x+1] = lz[x];
}
if (seg[2*x+2] < lz[x]) {
seg[2*x+2] = lz[2*x+2] = lz[x];
}
lz[x] = -1;
}
void set(int l, int r, int v, int x, int lx, int rx) {
if (lx >= r || rx <= l) return;
if (lx >= l && rx <= r) {
if (seg[x] >= v) return;
seg[x] = lz[x] = v;
return;
}
pushdown(x);
int m=(lx+rx)/2;
set(l, r, v, 2*x+1, lx, m);
set(l, r, v, 2*x+2, m, rx);
seg[x] = min(seg[2*x+1], seg[2*x+2]);
}
void set(int l, int r, int v) {
set(l, r, v, 0, 0, n);
}
int get(int i, int x, int lx, int rx) {
if (rx-lx==1) {
return seg[x];
}
pushdown(x);
int m=(lx+rx)/2;
if (i<m)return get(i,2*x+1,lx,m);
return get(i, 2*x+2, m, rx);
}
int get(int i) {
return get(i, 0, 0, n);
}
};
signed main() {
int n,m;cin>>n>>m;
vector<int> a(n);
for (auto &x:a) cin>>x;
vector<Query> q;
vector<bool> ans(m, false);
for (int i=0;i<m;i++) {
Query qq;
qq.idx = i;
cin>>qq.l>>qq.r>>qq.k;
qq.l--;qq.r--;
if (qq.l == qq.r) {
ans[i] = true;
continue;
}
q.push_back(qq);
}
sort(q.begin(), q.end());
int pt = 0;
stack<tii> s;
Segtree sg(n);
vector<int> ans2(m);
for (int i=0;i<n;i++) {
while (s.size() && s.top()[2] <= a[i]) {
s.pop();
}
int last;
if (s.size()) {
last = s.top()[1]+1;
int first = s.top()[0];
int score = s.top()[2] + a[i];
sg.set(first, last, score);
}
else {
last = 0;
}
s.push({last, i, a[i]});
// for (int j=0;j<=i;j++) {
// cout<<sg.get(j)<<" ";
// }
// cout<<"\n";
while (pt < (int)q.size() && q[pt].r == i) {
int qt = q[pt].l;
int val = sg.get(qt);
ans[q[pt].idx] = (q[pt].k >= val);
ans2[q[pt].idx] = val;
pt++;
}
}
for (int i=0;i<m;i++) {
cout<<ans[i]<<"\n";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |