Submission #961148

#	Time	Username	Problem	Language	Result	Execution time	Memory
961148		Ice_man	Construction of Highway (JOI18_construction)	C++14	0 / 100	8 ms	14684 KiB

construction

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

*/

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

#define maxn 200005
#define maxlog 20
#define INF 1000000010
#define mod 1000000007
#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;
}

pair <int , int> tree[maxn * 4];
int lazy[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;
}

pair <int , int> _merge(pair <int , int> e1 , pair <int , int> e2)
{
    return {min(e1.X , e2.X) , max(e1.Y , e2.Y)};
}

pair <int , int> 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);

    ///pair <int , int> res1 = query(node * 2 , l , mid , ql , new_r);
    //pair <int , int> res2 = query(node * 2 + 1 , mid + 1 , r , new_l , qr);

    return _merge(query(node * 2 , l , mid , ql , new_r) , query(node * 2 + 1 , mid + 1 , r , new_l , qr));
}


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

    if(ql == l && qr == r)
    {
        lazy[node] = qval;
        tree[node] = {qval , 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];
int pom;

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


int query_fenwick(int pos)
{
    int ans = 0;

    for(int i = pos; i >= 1; i -= (i & -i))
        ans += fenwick[i];

    return ans;
}



int par[maxn] , lead[maxn];
int pp[maxn];
int n;

void add(int node , int qval)
{
    while(node)
    {
        update(1 , 1 , n , pp[lead[node]] , pp[node] , qval);
        node = par[lead[node]];
    }
}

vector <pair <int , int>> wi;

void add_seg(int ql , int qr)
{
    cout << "q " << ql << " " << qr << endl;
    int l , r , mid;

    while(ql <= qr)
    {
        l = ql - 1;
        r = qr;

        while(l + 1 < r)
        {
            cout << "bs in " << l << " " << r << endl;
            mid = (l + r) / 2;
            pair <int , int> pomm = query(1 , 1 , n , mid , qr);

            cout << pomm.X << " " << pomm.Y << endl;

            if(pomm.X == pomm.Y)
                r = mid;
            else
                l = mid;
        }

        cout << "query " << r << " " << qr << endl;

        pair <int , int> pomm = query(1 ,1 , n , r , qr);
        wi.push_back({pomm.X , qr - r + 1});
        qr = r - 1;

    }
}


long long do_query(int idx)
{
    //cout << "_ - _ " << idx << endl;
    long long inv = 0;
    wi.clear();

    while(idx != 0)
    {
        cout << "in" << " " << pp[lead[idx]] << " " << pp[idx] << " " << idx << endl;
        add_seg(pp[lead[idx]] , pp[idx]);
        //cout << "out" << endl;
        idx = par[lead[idx]];
    }

    cout << "------------------" << endl;
    for(pair <int , int> e : wi)
        cout << e.X << " " << e.Y << endl;
    cout << endl << "------------------" << endl;

    cout << "passed addition" << endl;

    for(int i = 0; i < wi.size(); i++)
    {
        inv += query_fenwick(wi[i].X - 1) * 1LL * wi[i].Y;
        //cout << "= _ = " << wi[i].X << endl;
        update_fenwick(wi[i].X , wi[i].Y);
    }

    for(pair <int , int> e : wi)
        update_fenwick(e.X , -e.Y);

    return inv;
}

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

vector <int> v[maxn];

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

    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 id;

void hld(int node , int _par , int c)
{
    id++;
    pp[node] = id;
    lead[node] = c;

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

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

        if(nb == h[node])
            continue;

        hld(nb , node , nb);
    }

}

//int n;
vector <int> sorted;
map <int , int> mem;
int c[maxn];
int x[maxn] , y[maxn];

void read_solve()
{
    ///update_fenwick(0 , 0);
    cin >> n;
    for(int i = 1 ;i <= n; i++)
    {
        cin >> c[i];
        sorted.pb(c[i]);
    }
    sort(sorted.begin() , sorted.end());

    for(int i = 0; i < n; i++)
    {
        if(i == 0)
            pom++;
        if(i != 0 && sorted[i] != sorted[i - 1])
            pom++;

        mem[sorted[i]]++;
    }

    ///cout << "! " << pom << endl;

    //control

    for(int i = 1; i <= n; i++)
        c[i] = mem[sorted[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]);
    }

    dfs(1 , 0 , 1);
    //control
    hld(1 , 0 , 1);
    //control

    /**cout << "----------------" << endl;
    for(int i = 1; i <= n; i++)
        cout << pp[i] << " ";
    cout << endl << "-----------------------" << endl;

    for(int i = 1; i <= n; i++)
        cout << par[i] << " ";
    cout << endl << "---------------------------" << endl;
*/
    for(int i = 1; i <= n; i++)
        update(1 , 1 , n , pp[i] , pp[i] , c[i]);
    //control

    for(int i = 1; i < n; i++)
    {
        cout << do_query(x[i]) << endl;
        add(y[i] , c[y[i]]);
    }

}




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 'long long int do_query(int)':
construction.cpp:204:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |     for(int i = 0; i < wi.size(); i++)
      |                    ~~^~~~~~~~~~~

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