Submission #558585

#	Time	Username	Problem	Language	Result	Execution time	Memory
558585		urosk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	30 / 100	1506 ms	251784 KiB

sortbooks

// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll 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;
}
struct node{
    ll lf,rf,ok;
};
node mrg(node a,node b){
    node c;
    if(a.ok==-1) return b;
    if(b.ok==-1) return a;
    c.lf = a.lf;
    c.rf = b.rf;
    c.ok = 0;
    if((a.ok==1)&&(b.ok==1)&&(b.lf>=a.rf)) c.ok = 1;
    return c;
}
node seg[4*maxn];

void init2(ll v,ll tl,ll tr){
    if(tl==tr){
        seg[v].lf = a[tl];
        seg[v].rf = a[tl];
        seg[v].ok = 1;
        return;
    }
    ll mid = (tl+tr)/2;
    init2(2*v,tl,mid);
    init2(2*v+1,mid+1,tr);
    seg[v] = mrg(seg[2*v],seg[2*v+1]);
}
node get2(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return {0,0,-1};
    if(tl==l&&tr==r) return seg[v];
    ll mid = (tl+tr)/2;
    return mrg(get2(2*v,tl,mid,l,min(mid,r)),get2(2*v+1,mid+1,tr,max(mid+1,l),r));
}
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];
    if(n>5000){
        init2(1,1,n);
        while(q--){
            ll l,r; cin >> l >> r >> mood;
            cout<<get2(1,1,n,l,r).ok<<endl;
        }
        return 0;
    }
    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

5 2
1 2 3 4 5
1 3 0
2 5 0

5 2
1 3 2 5 4
1 3 0
1 2 0
*/

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23