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;
const int MAX = (1 << 20) + 10;
struct Node {
int mx;
int val;
Node () {
this->mx = -INT_MAX, this->val = 0;
}
Node(int mx) {
this->mx = mx, this->val = 0;
}
} vec[2 * MAX];
struct SegmentTree {
vector<int> nodes;
vector<int> v[2 * MAX];
int sz;
Node merge(Node &left, int ind) {
Node ans = {max(left.mx, vec[ind].mx)};
ans.val = max(left.val, vec[ind].val);
if (vec[ind].mx < left.mx) {
ans.val = max(ans.val, left.mx + vec[ind].mx);
} else if (v[ind][0] < left.mx) {
ans.val = max(ans.val, *(--lower_bound(v[ind].begin(), v[ind].end(), left.mx)) + left.mx);
}
return ans;
}
int query(int l, int r) {
r += 1;
vector<int> vec1, vec2;
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
vec1.push_back(l++);
}
if (r & 1) {
vec2.push_back(--r);
}
}
reverse(vec2.begin(), vec2.end());
for (int x: vec2) {
vec1.push_back(x);
}
Node ans = vec[vec1[0]];
for (int i = 1; i < vec1.size(); i++) {
ans = merge(ans, vec1[i]);
}
return ans.val;
}
void build(int dum, int tl, int tr) {
if (tl == tr) {
vec[dum] = Node(nodes[tl]);
v[dum] = {nodes[tl]};
} else {
build(2 * dum, tl, (tl + tr) / 2), build(2 * dum + 1, (tl + tr) / 2 + 1, tr);
vec[dum] = merge(vec[2 * dum], 2 * dum + 1);
std::merge(v[2 * dum].begin(), v[2 * dum].end(),
v[2 * dum + 1].begin(), v[2 * dum + 1].end(),
std::back_inserter(v[dum]));
}
}
SegmentTree(vector<int> nodes) {
this->nodes = nodes;
int n = nodes.size();
n = (1 << (int) log2(n)) * 2;
this->sz = n;
this->nodes.reserve(2 * sz);
while (this->nodes.size() < 2 * sz) {
this->nodes.push_back((int) 1e9);
}
build(1, 0, sz - 1);
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
SegmentTree st(v);
while (q--) {
int l, r, k;
cin >> l >> r >> k;
l--, r--;
cout << (st.query(l, r) <= k) << '\n';
}
}
Compilation message (stderr)
sortbooks.cpp: In member function 'int SegmentTree::query(int, int)':
sortbooks.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 1; i < vec1.size(); i++) {
| ~~^~~~~~~~~~~~~
sortbooks.cpp: In constructor 'SegmentTree::SegmentTree(std::vector<int>)':
sortbooks.cpp:75:35: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
75 | while (this->nodes.size() < 2 * sz) {
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~
# | 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... |