#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <cassert>
#include <algorithm>
using namespace std;
struct Node {
int mx;
int mn;
int val;
vector<int> v;
Node (int mn, int mx) {
this->mx = mx, this->mn = mn, this->val = 0;
}
};
struct SegmentTree {
vector<Node> vec;
vector<int> nodes;
Node merge (Node &left, Node &right) {
Node ans = {min(left.mn, right.mn), max(left.mx, right.mx)};
ans.val = max(left.val, right.val);
if (right.mx < left.mx) {
ans.val = max(ans.val, left.mx + right.mx);
} else if (right.mn < left.mx) {
int l = 0;
int r = right.v.size() - 1;
while (l != r) {
int m = (l + r + 1)/2;
if (right.v[m] < left.mx) {
l = m;
} else {
r = m - 1;
}
}
ans.val = max(ans.val, right.v[l] + left.mx);
}
return ans;
}
vector<int> intervals;
void query (int dum, int tl, int tr, int l, int r) {
if (tl >= l && tr <= r) {
intervals.push_back(dum);
} else if (tl <= r && tr >= l) {
query(2 * dum + 1, tl, (tl + tr)/2,l, r), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r);
}
}
int query (int l, int r) {
intervals.clear();
query(0, 0, (int)vec.size()/2 - 1, l, r);
Node ans = vec[intervals[0]];
for (int i = 1; i < intervals.size(); i++) {
ans = merge(ans, vec[intervals[i]]);
}
return ans.val;
}
void build (int dum, int tl, int tr) {
if (tl == tr) {
vec[dum] = Node(nodes[tl], nodes[tl]);
vec[dum].v = {nodes[tl]};
} else {
build(2 * dum + 1, tl, (tl + tr)/2), build(2 * dum + 2, (tl + tr)/2 + 1, tr);
vec[dum] = merge(vec[2 * dum + 1], vec[2 * dum + 2]);
vec[dum].v.reserve(vec[2 * dum + 1].v.size() + vec[2 * dum + 2].v.size());
std::merge(vec[2 * dum + 1].v.begin(), vec[2 * dum + 1].v.end(),
vec[2 * dum + 2].v.begin(), vec[2 * dum + 2].v.end(),
std::back_inserter(vec[dum].v));
}
}
SegmentTree (vector<int> nodes) {
this->nodes = nodes;
int n = nodes.size();
n = (1 << (int)log2(n)) * 2;
vec.assign(2 * n, Node(INT_MAX, -INT_MAX));
this->nodes.reserve(vec.size());
while (this->nodes.size() < vec.size()) {
this->nodes.push_back((int)1e9);
}
build(0, 0, (int)vec.size()/2 - 1);
}
};
inline char getChar() {
static char buf[1 << 16];
static int ps = 0, sz = 0;
if (ps == sz) {
ps = 0;
sz = fread(buf, sizeof(buf[0]), sizeof(buf) / sizeof(buf[0]), stdin);
}
return buf[ps++];
}
inline int ni() {
char c = getChar();
for (; c == '\n' || c == ' ';) c = getChar();
int o = 0;
for (; c != ' ' && c != '\n'; c = getChar()) o = o * 10 + c - '0';
return o;
}
inline void putChar(int c) {
static char buf[1 << 16];
static int pos = 0;
if (c == EOF || pos == 1 << 16) {
fwrite(buf, sizeof(buf[0]), pos, stdout);
pos = 0;
}
if (c == EOF) return;
buf[pos++] = c;
}
inline void printInt(int val) {
static char buf[12];
int pos = 0, sign = val < 0 ? -1 : 1;
val = abs(val);
if (val == 0) buf[pos++] = 48;
for (; val; val /= 10) buf[pos++] = 48 + val % 10;
if (sign == -1) buf[pos++] = '-';
buf[pos] = '\n';
for (; pos >= 0;) putChar(buf[pos--]);
}
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 = ni(), r = ni(), k = ni();
l--, r--;
cout << (st.query(l, r) <= k) << '\n';
}
}
Compilation message
sortbooks.cpp: In member function 'int SegmentTree::query(int, int)':
sortbooks.cpp:54:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for (int i = 1; i < intervals.size(); i++) {
| ~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1529 ms |
234088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
115 ms |
27972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
