Submission #1147283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147283		Math4Life2020	Weirdtree (RMI21_weirdtree)	C++20	5 / 100	2114 ms	385504 KiB

weirdtree

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

const ll Nm = (1<<19); const ll E = 19; const ll INF = 2e9;
map<int,int> stn[2*Nm];
ll stm[2*Nm];
ll sts[2*Nm];
ll lz[2*Nm];
ll N;

void initialise(int _N, int _Q, int h0[]) {
    N = _N;
    for (ll i=0;i<N;i++) {
        stn[i+Nm][h0[i+1]]=1;
        lz[i+Nm]=INF;
        sts[i+Nm]=h0[i+1];
        stm[i+Nm]=h0[i+1];
    }
    for (ll i=N;i<Nm;i++) {
        stn[i+Nm][0]=1;
        lz[i+Nm]=INF;
        sts[i+Nm]=0;
        stm[i+Nm]=0;
    }
    for (ll p=(Nm-1);p>=1;p--) {
        for (pii p0: stn[2*p]) {
            stn[p][p0.first]+=p0.second;
        }
        for (pii p0: stn[2*p+1]) {
            stn[p][p0.first]+=p0.second;
        }
        sts[p]=sts[2*p]+sts[2*p+1];
        stm[p]=max(stm[2*p],stm[2*p+1]);
        lz[p]=INF;
    }
    // for (ll p=1;p<(2*Nm);p++) {
    //     cout << "sts[p="<<p<<"]="<<sts[p]<<"\n";
    // }
}

void lft(ll h0, ll hf, ll qt, ll p) {
    //DO NOT PUSH DOWN
    if (p==0) {
        return;
    }
    sts[p]+=qt*(hf-h0);
    stn[p][hf]+=qt;
    stn[p][h0]-=qt;
    if (stn[p][h0]==0) {
        stn[p].erase(h0);
    }
    stm[p]=(*(--stn[p].end())).first;
    lft(h0,hf,qt,p/2);
}

void pdn(ll p) {
    if (p==0 || lz[p]==INF) {
        return;
    }
    while (!stn[p].empty()) {
        auto A0 = --stn[p].end();
        pii pf = *A0;
        if (pf.first<=lz[p]) {
            break;
        } else {
            //cout << "push down pdn at p="<<p<<"\n";
            //cout << "lz[p]="<<lz[p]<<", pf="<<pf.first<<","<<pf.second<<"\n";
            sts[p]-=(pf.first-lz[p])*pf.second;
            stm[p]=lz[p];
            stn[p].erase(A0);
            stn[p][lz[p]]+=pf.second;
        }  
    }
    if (p<Nm) {
        lz[2*p]=min(lz[2*p],lz[p]);
        lz[2*p+1]=min(lz[2*p+1],lz[p]);
    }
    lz[p]=INF;
}

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

void cut2(ll p, ll mval, ll k) {
    //cout << "cut2: p,mval,k="<<p<<","<<mval<<","<<k<<"\n";
    if (k==0) {
        return;
    }
    for (ll e=E;e>=0;e--) {
        pdn(p>>e);
    }
    if (stn[p][mval]==k) {
        lft(mval,mval-1,k,p);
        lz[p]=mval-1;
        return;
    }
    assert(p<Nm);
    if (stn[2*p].find(mval)==stn[2*p].end()) {
        cut2(2*p+1,mval,k);
    } else if (stn[2*p][mval]>=k) {
        cut2(2*p,mval,k);
    } else {
        cut2(2*p+1,mval,k-stn[2*p][mval]);
        //cout << "loopbk\n";
        cut2(2*p,mval,stn[2*p][mval]);
    }
}

void cut(int l, int r, int k) {
    if (k==0) {
        return;
    }
    l--; r--;
    ll l0 = l; ll r0 = r;
    ll mval = 0;
    vector<pii> vc;
    while (l0<=r0) {
        ll vl = v2(l0); ll vr = v2(r0+1);
        if (vl<vr) {
            ll p0 = (l0>>vl)+(1<<(E-vl));
            for (ll e=E;e>=0;e--) {
                pdn(p0>>e);
            }
            if (stm[p0]>mval) {
                vc.clear();
                mval = stm[p0];
            }
            if (stm[p0]==mval) {
                vc.push_back({l,p0});
            }
            l0+=(1<<vl);
        } else {
            ll p0 = (r0>>vr)+(1<<(E-vr));
            for (ll e=E;e>=0;e--) {
                pdn(p0>>e);
            }
            if (stm[p0]>mval) {
                vc.clear();
                mval = stm[p0];
            }
            if (stm[p0]==mval) {
                vc.push_back({r,p0});
            }
            r0-=(1<<vr);
        }
    }
    if (mval==0) {
        return;
    }
    sort(vc.begin(),vc.end());
    for (pii PQ: vc) {
        if (k==0) {
            return;
        }
        ll p0 = PQ.second;
        if (stn[p0][mval]<=k) {
            k -= stn[p0][mval];
            lz[p0]=min(lz[p0],mval-1);
            lft(mval,mval-1,stn[p0][mval],p0);
        } else {
            cut2(p0,mval,k);
            k=0;
        }
    }
    cut(l+1,r+1,k);
}

void magic(int i, int x) {
    i--;
    for (ll e=E;e>=0;e--) {
        pdn((i>>e)+(1<<(E-e)));
    }
    ll ht0 = (*stn[i+Nm].begin()).first;
    lft(ht0,x,1,i+Nm);
}

ll inspect(int l, int r) {
    ll fval = 0;
    l--; r--;
    ll l0=l; ll r0=r;
    while (l0<=r0) {
        ll vl = v2(l0); ll vr = v2(r0+1);
        if (vl<vr) {
            ll p0 = (l0>>vl)+(1<<(E-vl));
            for (ll e=E;e>=0;e--) {
                pdn(p0>>e);
            }
            fval += sts[p0];
            l0 += (1<<vl);
        } else {
            ll p0 = (r0>>vr)+(1<<(E-vr));
            for (ll e=E;e>=0;e--) {
                pdn(p0>>e);
            }
            fval += sts[p0];
            r0 -= (1<<vr);
        }
    }
    return fval;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 19
• Subtask 5: 0 / 10
• Subtask 6: 0 / 21
• Subtask 7: 0 / 29