Submission #1191030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191030		Math4Life2020	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	887 ms	327680 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std; 
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = (1LL<<20); const ll E = 20;
const ll INF = 1e18;

set<int> st[2*Nm];
ll inv[2*Nm];

ll v2(ll x) {
    return __builtin_ctz(x);
}

vector<int> qry(ll l, ll r) {
    //return (vector<int>(0));
    if (l>r) return (vector<int>(0));
    ll vl = v2(l); ll vr = v2(r+1);
    if (vl<vr) {
        vector<int> vfin;
        vfin.push_back((l>>vl)+(1<<(E-vl)));
        vector<int> vlz = qry(l+(1<<vl),r);
        for (ll x0: vlz) {
            vfin.push_back(x0);
        }
        return vfin;
    } else {
        vector<int> vfin = qry(l,r-(1<<vr));
        vfin.push_back((r<<vr)+(1<<(E-vr)));
        return vfin;
    }
}

ll qry2(ll l, ll r) {
    //return -INF;
    if (l>r) {
        return -INF;
    }
    ll vl = v2(l); ll vr = v2(r+1);
    if (vl<vr) {
        return max(inv[(l>>vl)+(1<<(E-vl))],qry2(l+(1<<vl),r));
    } else {
        return max(qry2(l,r-(1<<vr)),inv[(r>>vr)+(1<<(E-vr))]);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    ll N,M; cin >> N >> M;
    for (ll i=0;i<N;i++) {
        ll w; cin >> w;
        for (ll e=0;e<=E;e++) {
            ll p = (i>>e)+(1LL<<(E-e));
            st[p].insert(w);
        }
    }
    for (ll p=(Nm-1);p>=1;p--) {
        inv[p]=max(inv[2*p],inv[2*p+1]);
        if (st[2*p].size()==0) {
            continue;
        }
        ll mx0 = *(--(st[2*p].end()));
        if (st[2*p+1].size()!=0) {
            auto A0 = st[2*p+1].lower_bound(mx0);
            if (A0!=st[2*p+1].begin()) {
                A0--;
                inv[p]=max(inv[p],mx0+(*A0));
            }
        }
    }
    for (ll m=0;m<M;m++) {
        ll l,r,k; cin >> l >> r >> k;
        l--; r--;
        vector<int> vref = qry(l,r);
        ll ans = qry2(l,r);
        ll rmax = -INF;
        for (ll x0: vref) {
            //cout << "x0="<<x0<<"\n";
            if (st[x0].empty()) {
                continue;
            }
            auto A0 = st[x0].lower_bound(rmax);
            if (A0!=st[x0].begin()) {
                A0--;
                ans = max(ans,rmax+*A0);
            }
            if (st[x0].size()!=0) {
                rmax = max(rmax,(ll)*(--(st[x0].end())));
            }
        }
        //cout << "rmax="<<rmax<<"\n";
        //cout << "ans="<<ans<<"\n";
        cout << ((ans<=k) ? "1\n" : "0\n");
    }
}

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