#include <bits/stdc++.h>
#ifdef ONPC
#include "t_debug.cpp"
#else
#define debug(...) 42
#endif
using namespace std;
//namespace pbds = __gnu_pbds;
using ll = long long;
const int inf = 1e9;
const ll infl = 1e18;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rng(RANDOM);
template<typename T, typename U> istream& operator>>(istream& is, pair<T, U>& p) { return is >> p.first >> p.second; }
template<typename Cont> int sz(const Cont& cont) { return int(cont.size()); }
const string fileio = "";
constexpr int tests = 0, nmax = 2e5, nlog = __lg(nmax), mod = 1e9+7;
struct SegmentTree {
using T = int;
using S = int;
const T id = {};
inline T single(S v) { return v; }
T merge(const T& l, const T& r) {
return max(l, r);
}
int n;
vector<T> tree;
SegmentTree(int n) : n(n) {
tree.resize(n * 2, id);
build();
}
SegmentTree(vector<S> arr) : n(arr.size()) {
tree.resize(n * 2, id);
for (int i = 0; i < n; i++) {
tree[i + n] = single(arr[i]);
}
build();
}
void build() {
for (int i = n-1; i >= 1; i--) {
tree[i] = merge(tree[i*2], tree[i*2 + 1]);
}
}
void update(int i, S v) {
tree[i+=n] = single(v);
for (i /= 2; i >= 1; i/= 2)
tree[i] = merge(tree[i*2], tree[i*2+1]);
}
T queryit(int l, int r) {
T left = id, right = id;
l += n;
r += n;
while (l <= r) {
if (l % 2 == 1) left = merge(left, tree[l++]);
if (r % 2 == 0) right = merge(right, tree[r--]);
l /= 2; r /= 2;
}
return merge(left, right);
}
int find_first(function<bool(T&)> predicate, int last = 0) {
int v = 1;
while (v < n) {
if (predicate(tree[v*2 + last])) v = v*2 + last;
else if (predicate(tree[v*2 + !last])) v = v*2 + !last;
else return -1;
}
return v;
}
};
int solve() {
int n, m;
cin >> n >> m;
if (!cin) return 1;
vector<int> w(n);
for (auto& i : w) cin >> i;
vector<int> ix(n);
iota(ix.begin(), ix.end(), 0);
sort(ix.begin(), ix.end(), [&](int a, int b) {
return w[a] > w[b];
});
vector<tuple<int,int,int,int>> q(m);
vector<int> ans(m);
for (int i = 0; i < m; i++) {
int l, r, k;
cin >> l >> r >> k;
q[i] = {r, l, k, i};
}
sort(q.begin(), q.end());
SegmentTree tree(1<<20);
vector<pair<int,int>> st;
int j = 0;
for (auto [r, l, k, i] : q) {
while (j <= r && j < n) {
while (st.size() && st.back().first <= w[j]) {
st.pop_back();
};
if (st.size()) {
int k = st.back().second;
tree.update(k, w[j] + w[k]);
}
st.emplace_back(w[j], j);
j++;
}
ans[i] = tree.queryit(l, r) <= k;
}
for (int i : ans) cout << i << '\n';
return 0;
}
signed main() {
int t = 1;
#ifdef ONPC
t = 10000;
#else
if (fileio.size()) {freopen((fileio+".in").c_str(),"r",stdin);freopen((fileio+".out").c_str(),"w",stdout);}
#endif
cin.tie(0)->sync_with_stdio(0);
if (tests) cin >> t;
while (t-- && cin) {
if (solve()) break;
#ifdef ONPC
cout << "____________________" << endl;
#endif
}
return 0;
}
/*
█████ █████ ███ ████
▒▒███ ▒▒███ ▒▒▒ ▒▒███
███████ ████████ ███████ ████ ▒███ █████ ████ ██████ ████████
███▒▒███ ▒▒███▒▒███ ███▒▒███ ▒▒███ ▒███ ▒▒███ ▒███ ███▒▒███▒▒███▒▒███
▒███ ▒███ ▒███ ▒▒▒ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒▒▒
▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███ ▒███
▒▒████████ █████ ▒▒████████ █████ █████ ▒▒███████ ▒▒██████ █████
▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒ ▒▒▒▒▒███ ▒▒▒▒▒▒ ▒▒▒▒▒
███ ▒███
▒▒██████
▒▒▒▒▒▒
*/
Compilation message
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:129:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | if (fileio.size()) {freopen((fileio+".in").c_str(),"r",stdin);freopen((fileio+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:129:74: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
129 | if (fileio.size()) {freopen((fileio+".in").c_str(),"r",stdin);freopen((fileio+".out").c_str(),"w",stdout);}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
8452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
8452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
897 ms |
38236 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
76 ms |
13416 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
8452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 2 |
Correct |
5 ms |
8532 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
8452 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
