Submission #1191068

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191068		Math4Life2020	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2552 ms	197512 KiB

sortbooks

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#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;
vector<int> vempty;

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

ll v2(ll x) {
    if (x==0) {
        return 50;
    }
    return __builtin_ctz(x);
}

ll l2(ll x) {
    return (31-__builtin_clz(x));
}

vector<int> qry(ll l, ll r) {
    //return (vector<int>(0));
    //cout << "l,r="<<l<<","<<r<<"\n";
    if (l>r) return (vempty);
    ll vl = v2(l); ll vr = v2(r+1);
    //cout << "vl,vr="<<vl<<","<<vr<<"\n";
    if (vl<vr) {
        vector<int> vfin = qry(l+(1<<vl),r);
        vfin.push_back((l>>vl)+(1<<(E-vl)));
        return vfin;
    } else {
        //cout << "new termR: "<<((r>>vr)+(1<<(E-vr)))<<"\n";
        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<(2*Nm);i++) {
        inv[i]=-INF;
    }
    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].push_back(w);
        }
    }
    for (ll i=0;i<(2*Nm);i++) {
        sort(st[i].begin(),st[i].end());
    }
    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);
            auto A0 = lower_bound(st[2*p+1].begin(),st[2*p+1].end(),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;
        ll xprev = -INF;
        vector<pii> vrefP;
        for (ll x0: vref) {
            ll lxcur = l2(x0);
            ll xcur = (x0-(1<<lxcur))<<(E-lxcur);
            vrefP.push_back({xcur,x0});
        }
        sort(vrefP.begin(),vrefP.end());
        bool isvalid = 1;
        for (pii p0: vrefP) {
            ll x0 = p0.second;
            //cout << "x0="<<x0<<"\n";
            if (st[x0].empty()) {
                continue;
            }
            ll lxcur = l2(x0);
            ll xcur = (x0-(1<<lxcur))<<(E-lxcur);
            //cout << "xcur = "<<xcur << "\n";
            //assert(xcur > xprev);
            xprev = xcur;
            ans = max(ans,inv[x0]);
            //auto A0 = st[x0].lower_bound(rmax);
            auto A0 = lower_bound(st[x0].begin(),st[x0].end(),rmax);
            if (A0!=st[x0].begin()) {
                A0--;
                ans = max(ans,rmax+(*A0));
            }
            if (st[x0].size()!=0) {
                rmax = max(rmax,(ll)*(--(st[x0].end())));
            }
            if (ans>k) {
                isvalid = 0; break;
            }
        }
        cout << isvalid << "\n";
    }
}

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