Submission #961330

#	Time	Username	Problem	Language	Result	Execution time	Memory
961330		Ice_man	Construction of Highway (JOI18_construction)	C++14	100 / 100	743 ms	35932 KiB

construction

/**
 ____    ____    ____    __________________    ____    ____    ____
||I ||  ||c ||  ||e ||  ||                ||  ||M ||  ||a ||  ||n ||
||__||  ||__||  ||__||  ||________________||  ||__||  ||__||  ||__||
|/__\|  |/__\|  |/__\|  |/________________\|  |/__\|  |/__\|  |/__\|

*/

#include <iostream>
#include <chrono>
#include <algorithm>
#include <map>
#include <vector>

#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cerr<<"passed"<<endl;

//#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
//#pragma GCC target("avx2")

using namespace std;

/**std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}*/

typedef pair <int , int> pii;

pii _merge(pii e1 , pii e2)
{
    return {min(e1.X , e2.X) , max(e1.Y , e2.Y)};
}

int n;
vector <int> v[maxn];
int c[maxn];
int pom;
int x[maxn] , y[maxn];

void read()
{
    pom = 0;
    cin >> n;

    for(int i = 1; i <= n; i++)
        cin >> c[i];
    vector <int> sorted;
    for(int i = 1; i <= n; i++)
        sorted.pb(c[i]);
    sort(sorted.begin() , sorted.end());

    map <int , int> id;
    for(int i = 0; i < sorted.size(); i++)
    {
        if(i == 0)
            pom++;
        if(i != 0 && sorted[i] != sorted[i - 1])
            pom++;

        id[sorted[i]] = pom;
    }

    for(int i = 1; i <= n; i++)
        c[i] = id[c[i]];

    for(int i = 1; i < n; i++)
    {
        cin >> x[i] >> y[i];

        v[x[i]].pb(y[i]);
        v[y[i]].pb(x[i]);
    }
}


int lazy[maxn * 4];
pii tree[maxn * 4];

void push(int node)
{
    if(lazy[node] == 0)
        return;

    tree[node * 2].X = lazy[node];
    tree[node * 2].Y = lazy[node];

    tree[node * 2 + 1].X = lazy[node];
    tree[node * 2 + 1].Y = lazy[node];

    lazy[node * 2] = lazy[node];
    lazy[node * 2 + 1] = lazy[node];

    lazy[node] = 0;
}



pii query(int node , int l , int r , int ql , int qr)
{
    if(ql > qr)
        return {1e9 , 0};

    if(ql == l && qr == r)
        return tree[node];

    push(node);
    int mid = (l + r) / 2;
    int new_l = max(mid + 1 , ql);
    int new_r = min(mid , qr);

    pii res1 = query(node * 2 , l , mid , ql , new_r);
    pii res2 = query(node * 2 + 1 , mid + 1 , r , new_l , qr);

    return _merge(res1 , res2);
}


void update(int node , int l , int r , int ql , int qr , int qval)
{
    if(ql > qr)
        return;

    if(ql == l && qr == r)
    {
        tree[node].X = qval;
        tree[node].Y = qval;

        lazy[node] = qval;
        return;
    }

    push(node);
    int mid = (l + r) / 2;
    int new_l = max(mid + 1 , ql);
    int new_r = min(mid , qr);

    update(node * 2 , l , mid , ql , new_r , qval);
    update(node * 2 + 1 , mid + 1 , r , new_l , qr , qval);

    tree[node] = _merge(tree[node * 2] , tree[node * 2 + 1]);
}


int fenwick[maxn];

void update_fenwick(int idx , int qval)
{
    for(int i = idx; i <= pom; i += (i & (-i)))
        fenwick[i] += qval;
}

int query_fenwick(int idx)
{
    int ans = 0;
    for(int i = idx; i >= 1; i -= (i & (-i)))
        ans += fenwick[i];
    return ans;
}


vector <pii> _try;

void new_segment(int from , int to)
{
    int l , r , mid;
    while(from <= to)
    {
        l = from - 1;
        r = to;

        while(l + 1 < r)
        {
            mid = (l + r) / 2;
            pii pomm = query(1 , 1 , n , mid , to);
            if(pomm.X == pomm.Y)
                r = mid;
            else
                l = mid;
        }

        pii pomm = query(1 , 1 , n , r , to);
        _try.push_back({pomm.X , to - r + 1});
        to = r - 1;
    }
}



int par[maxn];
int depth[maxn];
int sz[maxn];
int h[maxn];

void dfs(int node , int _par = 0 , int de = 1)
{
    sz[node] = 1;
    depth[node] = de;
    par[node] = _par;

    for(int nb : v[node])
    {
        if(nb == _par)
            continue;

        dfs(nb , node , de + 1);
        if(sz[nb] > sz[h[node]])
            h[node] = nb;
        sz[node] += sz[nb];
    }

}


int idx;
int pp[maxn];
int lead[maxn];

void hld(int node , int _par = 0 , int head = 1)
{
    lead[node] = head;
    idx++;
    pp[node] = idx;

    if(h[node] != 0)
        hld(h[node] , node , head);

    for(int nb : v[node])
    {
        if(nb == _par)
            continue;
        if(nb == h[node])
            continue;

        hld(nb , node , nb);
    }

}


void solve()
{
    //control
    dfs(1);
    //control
    hld(1);

    for(int i = 1; i <= n; i++)
        update(1 , 1 , n , pp[i] , pp[i] , c[i]);

    long long inv = 0;

    for(int i = 1; i < n; i++)
    {
        //control
        inv = 0;
        _try.clear();

        int node = x[i];
        while(node)
        {
            new_segment(pp[lead[node]] , pp[node]);
            node = par[lead[node]];
        }

        for(pii e : _try)
        {
            inv += query_fenwick(e.X - 1) * 1LL * e.Y;
            update_fenwick(e.X , e.Y);
        }

        for(pii e : _try)
            update_fenwick(e.X , -e.Y);

        node = y[i];
        while(node)
        {
            update(1 ,1 , n , pp[lead[node]] , pp[node] , c[y[i]]);
            node = par[lead[node]];
        }

        cout << inv << endl;
    }

}




int main()
{

/**#ifdef ONLINE_JUDGE /// promeni
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
#endif*/

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    //startT = std::chrono::high_resolution_clock::now();

    read();
    solve();


    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void read()':
construction.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for(int i = 0; i < sorted.size(); i++)
      |                    ~~^~~~~~~~~~~~~~~

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