| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1131163 | Gray | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++20 | 0 ms | 0 KiB |
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll int
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
// const ll INF = 2e18;
// const ll MOD = 1e9+7;
struct seg_tree{
struct node{
vector<ll> vals;
ll res;
};
vector<node> t;
ll sz, rsz;
seg_tree(ll N){
sz=N*4; rsz=N;
t.resize(sz);
}
void build(ll tl, ll tr, ll v, vector<ll> &a){
if (tl==tr){
t[v].vals.push_back(a[tl]);
t[v].res=0;
}else{
ll tm = (tl+tr)/2;
build(tl, tm, v*2, a);
build(tm+1, tr, v*2+1, a);
// cout << "SYATY" << endl;
assert(!(t[v*2].vals.empty() or t[v*2+1].vals.empty()));
t[v].vals.resize(tr-tl+1);
merge(t[v*2].vals.begin(), t[v*2].vals.end(), t[v*2+1].vals.begin(), t[v*2+1].vals.end(), t[v].vals.begin());
// cout << "EDN" << endl;
assert((ll)t[v].vals.size()==(tr-tl+1));
t[v].res=max(t[v*2].res, t[v*2+1].res);
ll ind = lower_bound(t[v*2+1].vals.begin(), t[v*2+1].vals.end(), t[v*2].vals.back())-t[v*2+1].vals.begin();
t[v].res=max(t[v].res, (ind-1>=0?t[v*2+1].vals[ind-1]+t[v*2].vals.back():0ll));
}
}
pair<ll, ll> query(ll tl, ll tr, ll v, ll l, ll r, ll pass_mx){
// cout << tl << "-" << tr << ln;
if (l>r) return {-INF, pass_mx};
else if (tl==l and tr==r){
// cout << tl << "-" << tr << "->" << t[v].res << ln;
if (pass_mx==-INF) return {t[v].res, t[v].vals.back()};
else{
ll ind = lower_bound(t[v].vals.begin(), t[v].vals.end(), pass_mx)-t[v].vals.begin();
ll res = max(t[v].res, (ind-1>=0?pass_mx+t[v].vals[ind-1]:0));
// cout << tl << "-" << tr << " : " << ind << "->" << (ind-1>=0?pass_mx+t[v].vals[ind-1]:0) << ln;
return {res, max(pass_mx, t[v].vals.back())};
}
}else{
ll tm = (tl+tr)/2;
pair<ll, ll> res1 = query(tl, tm, v*2, l, min(r, tm), pass_mx);
pass_mx=res1.ss;
pair<ll, ll> res2 = query(tm+1, tr, v*2+1, max(l, tm+1), r, pass_mx);
return {max(res1.ff, res2.ff), res2.ss};
}
}
void build(vector<ll> &a){
build(0, rsz-1, 1, a);
}
ll query(ll l, ll r){
// cout << "Start" << endl;
ll res= query(0, rsz-1, 1, l, r, -INF).ff;
// cout << "End" << endl;
return res;
}
};
void solve(){
ll n, m; cin >> n >> m;
vector<ll> a(n);
for (ll i=0; i<n; i++) cin >> a[i];
seg_tree tr(n);
tr.build(a);
// return;
while (m--){
ll l, r, k; cin >> l >> r >> k;
l--; r--;
ll res = tr.query(l, r);
// cout << res << " -> ";
if (res>k){
cout << 0 << ln;
}else{
cout << 1 << ln;
}
}
}
/*
6 8 7 9 7.5
*/
int main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto start = chrono::high_resolution_clock::now();
ll t=1;
// cin >> t >> n;
while (t--) solve();
#ifdef LOCAL
auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
#endif
}