Submission #1293322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293322		Math4Life2020	Tree (IOI24_tree)	C++20	100 / 100	233 ms	40140 KiB

tree

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

ll N; const ll Nm = 2e5+5;
map<ll,ll> snum[Nm];
ll madd[Nm]; //which one does this refer to? (memory address)
ll lans; //coefficient on l for ans
vector<ll> pupd; //inverse prefix sum for the updates

vector<ll> upd; //actual computed updates (subtract from ans)
vector<ll> nhull; //number hull from snum[madd[0]]

void init(vector<int> P, vector<int> W) {
    N = P.size();
    pupd = vector<ll>(N+1,0);
    lans = 0;
    vector<ll> fadj[N];
    for (ll x=0;x<N;x++) {
        snum[x].clear();
        madd[x]=x;
    }
    for (ll i=1;i<N;i++) {
        fadj[P[i]].push_back(i);
    }
    for (ll x=(N-1);x>=0;x--) {
        if (fadj[x].size()==0) {
            lans += W[x];
        } else {
            ll F = fadj[x].size();
            lans += (F-1)*W[x];
            ll zc = -1;
            ll msz = -1;
            for (ll y: fadj[x]) {
                ll z = madd[y];
                vector<pii> fupd; 
                ll flen = 0; //final length (#) of all updates
                ll diffr = 0; //SUM of all updates (if can apply all)
                while (!snum[z].empty()) {
                    pii p0 = *(--snum[z].end());
                    if (p0.first<=W[x]) {
                        break;
                    }
                    snum[z].erase((--snum[z].end()));
                    fupd.push_back({p0.first-W[x],p0.second});
                    pupd[flen]+=(p0.first-W[x]);
                    flen += p0.second;
                    diffr += p0.second*(p0.first-W[x]);
                    pupd[flen]-=(p0.first-W[x]);
                }
                if (flen != 0) {
                    if (snum[z].find(W[x])==snum[z].end()) {
                        snum[z][W[x]]=0;
                    }
                    snum[z][W[x]]+=flen;
                }
                //cout << "snum[z].size()="<<snum[z].size()<<"\n";
                if ((ll)(snum[z].size())>=(ll)msz) {
                    //cout << "f1\n";
                    msz = snum[z].size();
                    zc = z;
                }
            }
            if (zc==-1) {
                //cout << "af\n"; exit(0);
            }
            assert(zc!=-1);
            madd[x]=zc;
            for (ll y: fadj[x]) {
                ll z = madd[y];
                if (z!=zc) {
                    for (pii p0: snum[z]) {
                        if (snum[zc].find(p0.first)==snum[zc].end()) {
                            snum[zc][p0.first]=0;
                        }
                        snum[zc][p0.first]+=p0.second;
                    }
                    snum[z].clear();
                }
            }
            if (snum[zc].find(W[x])==snum[zc].end()) {
                snum[zc][W[x]]=0;
            }
            snum[zc][W[x]]+=(F-1);
        }
    }
    upd = vector<ll>(N+1,0);
    ll vupd = 0;
    ll tupd = 0;
    upd[0]=0;
    for (ll x=0;x<N;x++) {
        vupd += pupd[x];
        tupd += vupd;
        upd[x+1] = tupd;
    }
    nhull = vector<ll>(N+1,0);
    ll xhull = 0;
    ll thull = 0;
    nhull[0]=0;
    while (!snum[madd[0]].empty()) {
        auto A0 = (--snum[madd[0]].end());
        pii p0 = *A0;
        //cout << "p0 term: "<<p0.first<<","<<p0.second<<"\n";
        snum[madd[0]].erase(A0);
        ll m = p0.first; ll delx = p0.second;
        for (ll x=(xhull+1);x<=(xhull+delx);x++) {
            thull += m;
            nhull[x]=thull;
        }
        xhull += delx;
    }
    for (ll x=(xhull+1);x<=N;x++) {
        nhull[x]=thull;
    }
    // for (ll x=0;x<=N;x++) {
    //     cout << "nhull["<<x<<"]="<<nhull[x]<<"\n";
    //     cout << "upd["<<x<<"]="<<upd[x]<<"\n";
    // }
    // cout << "nhull[0]="<<nhull[0]<<"\n";
    // cout << "nhull[1]="<<nhull[1]<<"\n";
}

ll query(int L, int R) {
    //between val[R/L] and val[R/L+1]
    ll a = (R-L)/L; ll b = (R-L)/L+1;
    ll ka = L*(1+R/L)-R;
    ll kb = R-L*(R/L);
    a = min(a,N); b=min(b,N);
    ll ans = L*lans;
    ans -= ka*(upd[a]+nhull[a]);
    ans -= kb*(upd[b]+nhull[b]);
    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 18 / 18
• Subtask 4: 7 / 7
• Subtask 5: 11 / 11
• Subtask 6: 22 / 22
• Subtask 7: 19 / 19