#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;
Node () {
this->mx = INT_MIN, this->mn = INT_MAX, this->val = 0;
}
};
struct MergeSortTree {
vector<vector<int>> vec;
vector<int> v;
void build (int dum, int tl, int tr) {
for (int i = tl; i <= tr; i++) {
vec[dum].push_back(v[i]);
}
sort(vec[dum].begin(), vec[dum].end());
if (tl == tr) {
return;
}
build(2 * dum + 1, tl, (tl + tr)/2);
build(2 * dum + 2, (tl + tr)/2 + 1, tr);
}
int get (vector<int>& arr, int k) {
assert(!arr.empty());
if (arr[0] > k) {
return -INT_MAX;
}
int l = 0;
int r = (int)arr.size() - 1;
while (l != r) {
int m = (l + r + 1)/2;
if (arr[m] <= k) {
l = m;
} else {
r = m - 1;
}
}
return arr[l];
}
int query (int dum, int tl, int tr, int l, int r, int k) {
if (tl >= l && tr <= r) {
return get(vec[dum], k);
}
if (tl > r || l > tr) {
return -INT_MAX;
}
return max(query(2 * dum + 1, tl, (tl + tr)/2, l, r, k), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r, k));
}
int query (int l, int r, int k) {
//find the largest element <= k in the range [l...r]
//returns -INT_MAX if no such element is available
return query(0, 0, (int)vec.size()/2 - 1, l, r, k);
}
MergeSortTree (vector<int> v) {
assert(__builtin_popcount(v.size()) == 1);
this->v = v;
vec.resize(v.size() * 2);
build(0, 0, (int)vec.size()/2 - 1);
}
};
struct SegmentTree {
vector<Node> vec;
vector<int> nodes;
vector<vector<int>> values; //sorted list of values
MergeSortTree ms = MergeSortTree({0});
Node merge (Node left, Node right, int tm, int tr) {
Node ans = Node();
ans.mn = min(left.mn, right.mn);
ans.mx = max(left.mx, right.mx);
ans.val = max(ans.val, max(left.val, right.val));
if (left.mx > right.mn) {
int res = -INT_MAX;
for (int i = tm + 1; i <= tr; i++) {
if (nodes[i] < left.mx) {
res = max(res, nodes[i]);
}
}
ans.val = max(ans.val, res + left.mx); //something <=
}
return ans;
}
Node query (int dum, int tl, int tr, int l, int r) {
if (tl >= l && tr <= r) {
return vec[dum];
}
if (tl > r || tr < l) {
return {};
}
return merge(query(2 * dum + 1, tl, (tl + tr)/2,l, r), query(2 * dum + 2, (tl + tr)/2 + 1, tr, l, r), (tl + tr)/2, tr);
}
int query (int l, int r) {
return query(0, 0, (int)vec.size()/2 - 1, l, r).val;
}
Node build (int dum, int tl, int tr) {
for (int i = tl; i <= tr; i++) {
values[dum].push_back(nodes[i]);
}
sort(values[dum].begin(), values[dum].end());
if (tl == tr) {
vec[dum] = Node();
vec[dum].mn = vec[dum].mx = nodes[tl];
return vec[dum];
}
build(2 * dum + 1, tl, (tl + tr)/2);
build(2 * dum + 2, (tl + tr)/2 + 1, tr);
vec[dum] = merge( build(2 * dum + 1, tl, (tl + tr)/2), build(2 * dum + 2, (tl + tr)/2 + 1, tr), (tl + tr)/2, tr);
return vec[dum];
}
SegmentTree (vector<int> nodes) {
this->nodes = nodes;
int n = nodes.size();
n = (1 << (int)log2(n)) * 2;
this->values.resize(2 * n);
vec.assign(2 * n, Node());
while (this->nodes.size() < vec.size()) {
this->nodes.push_back((int)1e9);
}
this->ms = MergeSortTree(this->nodes);
build(0, 0, (int)vec.size()/2 - 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';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
49 ms |
1072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
49 ms |
1072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
592 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3039 ms |
66276 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
49 ms |
1072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
49 ms |
1072 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
