| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1210799 | vanea | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = 4e6+10;
ll st[mxN], n;
vector<ll> st1[mxN];
void build(int node, int l, int r, vector<ll> &v) {
if(l == r) {
st[node] = v[l];
st1[node].push_back(v[l]);
return ;
}
int mid = (l+r)/2;
build(node*2, l, mid, v);
build(node*2+1, mid+1, r, v);
st[node] = max(st[node*2], st[node*2+1]);
int i = 0, j = 0;
while(i < st1[node*2].size() && j < st1[node*2+1][size]) {
if(st1[node*2][i] <= st1[node*2+1][j]) {
st1[node].push_back(st1[node*2][i++]);
}
else {
st1[node].push_back(st1[node*2+1][j++]);
}
}
while(i < st1[node*2].size()) {
st1[node].push_back(st1[node*2][i++]);
}
while(j < st1[node*2+1].size()) {
st1[node].push_back(st1[node*2+1][j++]);
}
}
ll qry1(int node, int l, int r, int l1, int r1) {
if(l1 <= l && r <= r1) return st[node];
if(l1 > r || r1 < l) return -1;
int mid = (l+r)/2;
return max(qry1(node*2, l, mid, l1, r1),
qry1(node*2+1, mid+1, r, l1, r1));
}
bool qry(int node, int l, int r, int l1, int r1, ll k) {
if(l1 <= l && r <= r1) {
ll x = qry1(1, 0, n-1, l1, l-1);
if(x == -1) return false;
if(k-x >= x) return false;
auto it = lower_bound(st1[node].begin(), st1[node].end(), k-x);
if(it == st1[node].end()) return false;
if(*it >= x) return false;
return true;
}
if(l1 > r || r1 < l) return false;
int mid = (l+r)/2;
return (qry(node*2, l, mid, l1, r1, k) || qry(node*2+1, mid+1, r, l1, r1, k));
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int q;
cin >> n >> q;
vector<ll> v(n);
for(int i = 0; i < n; i++) {
cin >> v[i];
}
build(1, 0, n-1, v);
while(q--) {
int l, r; ll k;
cin >> l >> r >> k;
--l; --r; ++k;
bool ans = qry(1, 0, n-1, l, r, k);
cout << 1-(int)ans << '\n';
}
return 0;
}