Submission #84374

#	Time	Username	Problem	Language	Result	Execution time	Memory
84374		Alexa2001	Construction of Highway (JOI18_construction)	C++17	100 / 100	770 ms	156840 KiB

construction

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e5 + 5;
typedef long long ll;

struct Val
{
    int val, cnt;
};

vector<int> v[Nmax];
vector<Val> A;
int n, x[Nmax], y[Nmax], val[Nmax], t[Nmax];

struct AIB
{
    int a[Nmax], n;

    int ub(int x) { return (x&(-x)); }

    void update(int pos, int val)
    {
        for(; pos; pos-=ub(pos)) a[pos] += val;
    }

    int query(int pos)
    {
        int ans = 0;
        for(; pos<=n; pos+=ub(pos)) ans += a[pos];
        return ans;
    }

    void shrink(int n)
    {
        this->n = n;
        int i;
        for(i=0; i<=n; ++i) a[i] = 0;
    }
} aib;


namespace hld
{
    static int where[Nmax], pos[Nmax], w[Nmax];
    static vector<int> p[Nmax];
    static deque<Val> z[Nmax];

    void dfs(int node)
    {
        w[node] = 1;
        for(auto son : v[node])
        {
            dfs(son);
            w[node] += w[son];
        }
    }

    void prepare_chains(int node)
    {
        static int chains = 1;

        where[node] = chains;
        p[where[node]].push_back(node);
        pos[node] = p[where[node]].size();

        if(v[node].empty()) return;

        int xson = v[node][0];
        for(auto son : v[node])
            if(w[son] > w[xson]) xson = son;

        prepare_chains(xson);

        for(auto son : v[node])
            if(son != xson)
            {
                ++chains;
                prepare_chains(son);
            }
    }

    void path(int node, vector<Val> &A)
    {
        int s = 0, i, id = where[node], len = pos[node];
        vector<Val> curr;

        for(i=0; i<z[id].size() && s + z[id][i].cnt <= len; ++i)
        {
            curr.push_back(z[id][i]);
            s += z[id][i].cnt;
        }

        if(i < z[id].size())
            curr.push_back({ z[id][i].val, len - s });

        reverse(curr.begin(), curr.end());
        for(auto it : curr) A.push_back(it);

        if(id == 1) return;
        path(t[p[id][0]], A);
    }

    void update(int node, int val)
    {
        int id = where[node], len = pos[node];

        while(z[id].size() && len >= z[id][0].cnt) len -= z[id][0].cnt, z[id].pop_front();

        if(z[id].empty() && len == 1) /// this is the chain that includes the new node
        {
            z[id].push_back({val, pos[node]});
            if(id == 1) return;
            update(t[p[id][0]], val);
            return;
        }

        /// otherwise the current chain is a "normal" one

        if(z[id].size())
            z[id][0].cnt -= len;
        else assert(len == 0);

        z[id].push_front({val, pos[node]});

        if(id == 1) return;
        update(t[p[id][0]], val);
    }
};

ll solve(vector<Val> &A) /// count the number of inversions
{
    reverse(A.begin(), A.end());

    map<int,int> mp;
    for(auto it : A) mp[it.val] = 1;
    int cnt = 1;
    for(auto &it : mp) it.second = ++cnt;
    for(auto &it : A) it.val = mp[it.val];

    aib.shrink(cnt);
    ll ans = 0;
    for(auto &it : A)
    {
        ans += (ll) aib.query(it.val + 1) * it.cnt;
        aib.update(it.val, it.cnt);
    }
    return ans;
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    int i;
    cin >> n;
    for(i=1; i<=n; ++i) cin >> val[i];

    for(i=1; i<n; ++i)
    {
        cin >> x[i] >> y[i];
        v[x[i]].push_back(y[i]);
        t[y[i]] = x[i];
    }

    hld :: dfs(1);
    hld :: prepare_chains(1);
    hld :: z[1].push_back({val[1], 1});

    for(i=1; i<n; ++i)
    {
        A.clear();
        hld :: path(x[i], A);
        cout << solve(A) << '\n';
        hld :: update(y[i], val[y[i]]);
    }

    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void hld::path(int, std::vector<Val>&)':
construction.cpp:89:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0; i<z[id].size() && s + z[id][i].cnt <= len; ++i)
                  ~^~~~~~~~~~~~~
construction.cpp:95:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i < z[id].size())
            ~~^~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84