| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1267842 | usukhbaatar | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define heap priority_queue
#define endl '\n'
#define maxx(a, b) a = max(a, b)
#define minn(a, b) a = min(a, b)
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define rep1(i, n) for (int i = 1; i <= n; i++)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define int long long
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<string> vs;
template <class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const int mod = 1e9 + 7;
const int oo ((((1LL << 62) - 1) << 1) + 1);
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};
int n, q;
vi a;
vii b;
vector<array<int, 4>> queries;
pii meta(int i) { return {(i << 1) + 1, (i + 1) << 1}; }
tuple<int, int, int> meta(int i, int l, int r) {
pii m = meta(i); return { m.ff, m.ss, (l + r) / 2 };
}
vi val;
void update(int i, int tl, int tr, int k, int t) {
if (tl == tr) { val[i] = t; return; }
auto [x, y, tm] = meta(i, tl, tr);
if (k <= tm) update(x, tl, tm, k, t);
else update(y, tm + 1, tr, k, t);
val[i] = max(val[x], val[y]);
}
int query(int i, int tl, int tr, int l, int r) {
if (tl == l && r == tr) return val[i];
auto [x, y, tm] = meta(i, tl, tr);
if (r <= tm) return query(x, tl, tm, l, r);
else if (tm + 1 <= l) return query(y, tm + 1, tr, l, r);
return max(query(x, tl, tm, l, tm), query(y, tm + 1, tr, tm + 1, r));
}
int32_t main() {
fastio;
cin >> n >> q;
a.resize(n + 1); a[0] = 1e10;
b.resize(n + 1);
vi stk = {0};
rep1(i, n) {
cin >> a[i];
while(a[stk.back()] <= a[i]) stk.pop_back();
if (stk.size() > 1) {
queries.pb({-a[i] - a[stk.back()], 1, i, stk.back()});
b[i] = {a[i] + a[stk.back()], stl.back()};
}
stk.pb(i);
}
vi ans(q);
vi l(q), r(q);
rep(i, q) {
int k;
cin >> l[i] >> r[i] >> k;
for (int j = l[i]; j <= r[i]; j++) {
if (b[j].ff > k && b[j].ss >= l[i]) {
ans[i] = 1;
break;
}
}
queries.pb({-k, 0, i, 0});
}
// sort(all(queries));
// val.resize(4 * n);
// for (auto &qry : queries) {
// //cout << qry[0] << ' ' << qry[1] << ' ' << qry[2] << ' ' << qry[3] << endl;
// if (qry[1] == 1) update(0, 0, n - 1, qry[2] - 1, qry[3]);
// else {
// int id = qry[2];
// ans[id] = (query(0, 0, n - 1, l[id] - 1, r[id] - 1) >= l[id] ? 0 : 1);
// }
// }
for (int x : ans) cout << x << endl;
return 0;
}