| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 558458 | urosk | Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll short int
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 1000005
ll n,q;
ll a[maxn];
set<ll> t[4*maxn];
ll val[4*maxn];
ll mood;
bool moe = 1;
void init(ll v,ll tl,ll tr){
if(tl==tr){
t[v].insert(a[tl]);
return;
}
ll mid = (tl+tr)/2;
init(2*v,tl,mid);
init(2*v+1,mid+1,tr);
auto it = t[2*v].end(); it--;
ll x = *it;
it = t[2*v+1].lower_bound(x);
if(it==t[2*v+1].begin()){
val[v] = 0;
}else{
it--;
val[v] = x + *it;
}
val[v] = max(val[v],max(val[2*v],val[2*v+1]));
//here;
//cerr<<tl<< " "<<tr<<" "<<val[v]<<" "<<*it<<endl;
for(ll i = tl;i<=tr;i++) t[v].insert(a[i]);
}
set<ll> get(ll v,ll tl,ll tr,ll l,ll r){
if(l>r) return {};
if(tl==l&&tr==r){
if(val[v]>mood){
moe = 0;
return {};
}
return t[v];
}
ll mid = (tl+tr)/2;
set<ll> lf = get(2*v,tl,mid,l,min(mid,r));
set<ll> rf = get(2*v+1,mid+1,tr,max(mid+1,l),r);
if(moe==0) return {};
if(sz(lf)==0) return rf;
if(sz(rf)==0) return lf;
auto it = lf.end();
it--;
ll x = *it;
it = rf.lower_bound(x);
if(it==rf.begin()){
for(ll x : lf) rf.insert(x);
return rf;
}
it--;
if(x+*it>mood){
moe = 0;
return {};
}
for(ll x : lf) rf.insert(x);
return rf;
}
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> q;
for(ll i = 1;i<=n;i++) cin >> a[i];
init(1,1,n);
while(q--){
ll l,r; cin >> l >> r >> mood;
moe = 1;
get(1,1,n,l,r);
cout<<moe<<endl;
}
return 0;
}
/*
4 1
1 2 1 1
1 4 1
*/