Submission #1104950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104950		jerzyk	Tree (IOI24_tree)	C++17	100 / 100	145 ms	58920 KiB

tree

#include <bits/stdc++.h>
#include "tree.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
int drz[2 * N];
vector<int> aktv;
int pre[N], pos[N], rev[N];

ll wei[N];
ll inc[N * 5], sum[N * 5];
int il[N];
vector<int> ed[N];

void Change(int v, int x)
{
    v += N;
    drz[v] = x;
    v /= 2;
    while(v > 0)
    {
        drz[v] = max(drz[v * 2], drz[v * 2 + 1]);
        v /= 2;
    }
}

void Find(int v, int p, int k, int pz, int kz, int x)
{
    if(drz[v] <= x) return;
    if(p > kz || k < pz) return;
    if(v >= N)
    {
        drz[v] = -1;
        aktv.pb(rev[v - N]);
        return;
    }
    Find(v * 2, p, (p + k) / 2, pz, kz, x);
    Find(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz, x);
    drz[v] = max(drz[v * 2], drz[v * 2 + 1]);
}

bool C(int a, int b)
{
    return (wei[a] > wei[b]);
}

void DFS(int v, int &cnt)
{
    ++cnt; rev[cnt] = v; pre[v] = cnt; pos[v] = cnt;
    il[v] = max(0, (int)ed[v].size() - 1);
    Change(pre[v], wei[v]);

    if(ed[v].size() == 0)
        sum[0] += wei[v];
    else
        sum[0] += (ll)il[v] * wei[v];
    //cerr << "DFS: " << v << " " << wei[v] << "\n";

    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
        DFS(ed[v][i], cnt);
        pos[v] = pos[ed[v][i]];
        Find(1, 0, N - 1, pre[ed[v][i]], pos[ed[v][i]], wei[v]);
        sort(aktv.begin(), aktv.end(), C);
        int s = 0;
        for(int j = 0; j < (int)aktv.size(); ++j)
        {
            int ne = aktv[j];
            //cout << "R: " << v << " " << ne << "\n";
            inc[1 + s] += wei[v] - wei[ne];
            inc[1 + s + il[ne]] -= wei[v] - wei[ne];
            s += il[ne];
        }
        aktv.clear();
        il[v] += s;
    }
}

void init(vector<int> P, vector<int> W)
{
    for(int i = 1; i < 2 * N; ++i) drz[i] = -1;

    int n = (int)P.size() + 1;
    for(int i = 1; i < (int)P.size(); ++i)
        ed[P[i] + 1].pb(i + 1);
    for(int i = 0; i < n; ++i)
        wei[i + 1] = W[i];
    ed[0].pb(1);
    int xd = 0;
    DFS(0, xd);
    for(int i = 1; i <= 1000'000; ++i)
        inc[i] += inc[i - 1];
    for(int i = 1; i <= 1000'000; ++i)
        sum[i] = sum[i - 1] + inc[i - 1];
}

long long query(int L, int R)
{
    ll ans = sum[R / L] * (ll)L + inc[R / L] * (ll)(R % L);
    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