제출 #1147313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147313		Math4Life2020	Weirdtree (RMI21_weirdtree)	C++20	42 / 100	2118 ms	427916 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 = 1e9+5;
ll N;

map<int,int> stn[2*Nm]; //segtree of numbers
long long sts[2*Nm]; //segtree of sum
ll stm[2*Nm]; //segtree of max
ll st2m[2*Nm]; //segtree of 2nd max
//SEGTREE BEATS BABYYYYY
ll lz[2*Nm]; //lazy tag
ll h[Nm]; //actual values; don't store

void initialise(int _N, int _Q, int _h[]) {
    N = _N;
    for (ll i=0;i<N;i++) {
        h[i]=_h[i+1];
    }
    for (ll i=0;i<Nm;i++) {
        sts[i+Nm]=h[i];
        stm[i+Nm]=h[i];
        st2m[i+Nm]=-INF;
        stn[i+Nm][h[i]]=1;
        stn[i+Nm][-INF]=1;
    }
    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]);
        st2m[p]=max(st2m[2*p],st2m[2*p+1]);
        if (stm[2*p]!=stm[2*p+1]) {
            st2m[p]=max(st2m[p],min(stm[2*p],stm[2*p+1]));
        }
    }
    for (ll p=0;p<(2*Nm);p++) {
        lz[p]=INF;
    }
}

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

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

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

void pdnP(ll p0) {
    return;
    for (ll e=E;e>=0;e--) {
        pdn(p0>>e);
    }
}

void cut2(ll p0, ll k, ll lt) {
    // cout << "cut2: p0,k,lt="<<p0<<","<<k<<","<<lt<<"\n";
    // cout << "curr value: "<<stn[p0][lt]<<"\n";
    assert(k>=0);
    if (k==0 || lt==0 | p0==0) {
        return;
    }
    pdn(p0);
    pdnP(p0);
    assert(stn[p0][lt]>=k);
    //cout << "currF value: "<<stn[p0][lt]<<"\n";
    if (stn[p0][lt]==k) {
        lz[p0]=lt-1; 
    } else {
        assert(p0<Nm);
        pdn(2*p0);
        pdnP(2*p0);
        pdn(2*p0+1);
        pdnP(2*p0+1);
        if (stn[2*p0].find(lt)==stn[2*p0].end()) {
            cut2(2*p0+1,k,lt);
        } else if (stn[2*p0][lt]>=k) {
            cut2(2*p0,k,lt);
        } else {
            cut2(2*p0+1,k-stn[2*p0][lt],lt);
            cut2(2*p0,stn[2*p0][lt],lt);
        }
    }
    if (stn[p0][lt]==k) {
        sts[p0]-=k*lt;
        stn[p0].erase(lt);
    } else {
        stn[p0][lt]-=k;
        sts[p0]-=k*lt;
    }
    stn[p0][lt-1]+=k;
    sts[p0]+=k*(lt-1);
    auto A0 = (--stn[p0].end());
    stm[p0]=(*A0).first;
    A0--;
    st2m[p0]=(*A0).first;
}

void lft(map<ll,ll> m0, ll lt) {
    while (!m0.empty()) {
        pii pir = *(--m0.end()); m0.erase(--m0.end());
        ll p0 = pir.first; ll del = pir.second;
        //cout << "lft: p0,del,lt="<<p0<<","<<del<<","<<lt<<"\n";
        if (p0<1) {
            return;
        }
        sts[p0]+=lt*del;
        stn[p0][lt]+=del;
        //cout << "new val: "<<stn[p0][lt]<<"\n";
        if (stn[p0][lt]==0) {
            stn[p0].erase(stn[p0].find(lt));
        }
        auto A0 = (--stn[p0].end());
        stm[p0]=(*A0).first;
        A0--;
        st2m[p0]=(*A0).first;
        //cout << "new stm: "<<stm[p0]<<"\n";
        m0[p0/2]+=del;
    }
}

void cut(int l, int r, int k) {
    //cout << "CUT CALL\n";
    if (k<=0) {
        return;
    }
    l--; r--;
    for (ll e=E;e>=0;e--) {
        pdn((l>>e)+(1<<(E-e)));
        pdn((r>>e)+(1<<(E-e)));
        pdn((l>>e)+1+(1<<(E-e)));
        pdn((r>>e)-1+(1<<(E-e)));
    }
    ll lt = 0; vector<ll> vp0; vector<ll> vpc;
    ll l2t = 0;
    ll l0 = l; ll r0 = r;
    while (l0<=r0) {
        ll vl = v2(l0); ll vr = v2(r0+1);
        if (vl<vr) {
            ll pc = (l0>>vl)+(1<<(E-vl));
            vpc.push_back(pc);
            pdnP(pc);
            pdn(pc);
            if (stm[pc]>lt) {
                vp0.clear();
                vp0.push_back(pc);
                //l2t = max(l2t,lt);
                lt = stm[pc];
            } else if (stm[pc]==lt) {
                vp0.push_back(pc);
            } else {
                //l2t = max(l2t,stm[pc]);
            }
            //l2t = max(l2t,st2m[pc]);
            l0 += (1<<vl);
        } else {
            ll pc = (r0>>vr)+(1<<(E-vr));
            vpc.push_back(pc);
            pdnP(pc);
            pdn(pc);
            if (stm[pc]>lt) {
                vp0.clear();
                vp0.push_back(pc);
                //l2t = max(l2t,lt);
                lt = stm[pc];
            } else if (stm[pc]==lt) {
                vp0.push_back(pc);
            }
            //l2t = max(l2t,st2m[pc]);
            r0 -= (1<<vr);
        }
    }
    if (lt==0) {
        return;
    }
    for (ll p0: vpc) {
        if (stm[p0]==lt) {
            l2t = max(st2m[p0],l2t);
        } else {
            l2t = max(stm[p0],l2t);
        }
    }
    vector<pii> vpn; 
    for (ll p0: vp0) {
        ll lp = l2(p0);
        ll xn = (p0-(1<<lp))<<(E-lp);
        vpn.push_back({xn,p0});
    }
    sort(vpn.begin(),vpn.end());
    vp0.clear();
    for (pii p1: vpn) {
        vp0.push_back(p1.second);
    }
    // for (ll p0: vp0) {
    //     cout << "p0 in vp0: "<<p0<<"\n";
    // }
    ll PDEL = -1;
    map<ll,ll> lftm;
    //cout << "lt="<<lt<<"\n";
    //cout << stn[2][2]<<"\n";
    ll nsum = 0;
    for (ll p0: vp0) {
        if (stn[p0].find(lt)==stn[p0].end()) {
            continue;
        }
        nsum += stn[p0][lt];
    }
    ll REV=0;
    REV = min(k/nsum,lt-l2t);
    if (REV>0) {
        map<ll,ll> lftm2;
        for (ll p0: vp0) {
            //cout << "k="<<k<<", p0="<<p0<<", lt="<<lt<<", stn[p0][lt]="<<stn[p0][lt]<<"\n";
            if (stn[p0].find(lt)==stn[p0].end()) {
                continue;
            }
            lftm[p0]+= -stn[p0][lt];
            lftm2[p0]+= stn[p0][lt];
            k -= REV*stn[p0][lt];
            lz[p0]=min(lz[p0],lt-REV);
        }
        lft(lftm2,lt-REV);
        lft(lftm,lt);
        for (ll p0: vp0) {
            assert(stm[p0]>=(lt-REV));
        }
        cut(l+1,r+1,k);
        return;
    }
    for (ll p0: vp0) {
        //cout << "k="<<k<<", p0="<<p0<<", lt="<<lt<<", stn[p0][lt]="<<stn[p0][lt]<<"\n";
        if (stn[p0][lt]<=k) {
            lftm[p0]+= -stn[p0][lt];
            k -= stn[p0][lt];
            lz[p0]=min(lz[p0],lt-1);
        } else {
            PDEL = p0;
            break;
        }
        if (k==0) {
            break;
        }
    }
    if (PDEL!=-1) {
        cut2(PDEL,k,lt);
        lftm[PDEL/2] += -k;
        k=0;
    }
    map<ll,ll> lftm2;
    for (pii p0: lftm) {
        lftm2[p0.first]=-p0.second;
    }
    lft(lftm2,lt-1);
    lft(lftm,lt);
    for (ll p0: vp0) {
        pdn(p0);
    }
    if (PDEL==-1 && 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 h0 = stm[i+Nm];
    map<ll,ll> m0;
    m0[i+Nm]=1;
    lft(m0,x);
    map<ll,ll> m1;
    m1[i+Nm]=-1;
    lft(m1,h0);
}

long long inspect(int l, int r) {
    l--; r--;
    long long fval = 0;
    for (ll e=E;e>=0;e--) {
        pdn((l>>e)+(1<<(E-e)));
        pdn((r>>e)+(1<<(E-e)));
        pdn((l>>e)+1+(1<<(E-e)));
        pdn((r>>e)-1+(1<<(E-e)));
    }
    while (l<=r) {
        ll vl = v2(l); ll vr = v2(r+1);
        if (vl<vr) {
            pdnP((l>>vl)+(1<<(E-vl)));
            pdn((l>>vl)+(1<<(E-vl)));
            fval += sts[(l>>vl)+(1<<(E-vl))];
            //cout << "l,vl="<<l<<","<<vl<<"\n";
            //cout << "ins="<<((l>>vl)+(1<<(E-vl)))<<", outs="<<sts[(l>>vl)+(1<<(E-vl))]<<"\n";
            l += (1<<vl);
        } else {
            pdnP((r>>vr)+(1<<(E-vr)));
            pdn((r>>vr)+(1<<(E-vr)));
            fval += sts[(r>>vr)+(1<<(E-vr))];
            //cout << "r,vr="<<r<<","<<vr<<"\n";
            //cout << "ins="<<((r>>vr)+(1<<(E-vr)))<<", outs="<<sts[(r>>vr)+(1<<(E-vr))]<<"\n";
            r -= (1<<vr);
        }
    }
    return fval;
}

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