Submission #761752

#	Time	Username	Problem	Language	Result	Execution time	Memory
761752		fatemetmhr	Ideal city (IOI12_city)	C++11	100 / 100	148 ms	29792 KiB

city

//  ~ Be Name Khoda ~  //

#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e5   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  2e3   + 10;
const int mod   =  2e9;
const ll  inf   =  1e18;

__int128 ans = 0;
vector <int> avx, av[maxn5];
map <int, int> inner[maxn5];
int ptx[maxn5], par[maxn5];


struct __node{

    vector <int> adj;
    int n, inin;
    ll dissum, dissumup, nup;

    inline void clear(){
        n = inin = 0;
        dissum = dissumup = nup = 0;
        adj.clear();
    }

    inline void rebuild_adj(){
        sort(all(adj));
        adj.resize(unique(all(adj)) - adj.begin());
        adj.shrink_to_fit();
    }

    inline void sumup(int ty){
        //cout << "here " << ty << ' ' << dissum << ' ' << n << ' ' << dissumup << ' ' << nup << endl;
        if(ty != -1){
            dissum += dissumup;
            n += nup;
        }
        ans += __int128(dissum) * inin;
        //cout << "then " << dissum << ' ' << n << ' ' << inin << ' ' << ans << endl;
    }

} node[maxn5];

void dfs_up(int v){
    //cout << "aha " << v << ' ' << par[v] << ' ' << node[v].n << endl;
    for(auto u : node[v].adj) if(u != par[v]){
        par[u] = v;
        dfs_up(u);
        node[v].dissum += node[u].dissum + node[u].n;
        node[v].n += node[u].n;
    }
}

void dfs_dw(int v){
    //cout << "summing up " << v << endl;
    node[v].sumup(par[v]);
    for(auto u : node[v].adj) if(u != par[v]){
        node[u].dissumup = node[v].dissum + node[v].n - node[u].dissum - 2 * node[u].n;
        node[u].nup = node[v].n - node[u].n;
        dfs_dw(u);
    }
}

inline void solve(int n, int *x, int *y){
    avx.clear();
    for(int i = 0; i < n; i++)
        avx.pb(x[i]);
    sort(all(avx));
    avx.resize(unique(all(avx)) - avx.begin());
    for(int i = 0; i < avx.size(); i++){
        av[i].clear();
        inner[i].clear();
    }
    for(int i = 0; i < n; i++){
        ptx[i] = lower_bound(all(avx), x[i]) - avx.begin();
        av[ptx[i]].pb(y[i]);
    }
    int newid = 0;
    for(int i = 0; i < avx.size(); i++){
        sort(all(av[i]));
        int last = 0;
        for(int j = 1; j < av[i].size(); j++){
            if(av[i][j] != av[i][j - 1] + 1){
                node[newid].clear();
                node[newid].n = node[newid].inin = j - last;
                for(int k = last; k < j; k++)
                    inner[i][av[i][k]] = newid;
                newid++;
                last = j;
            }
        }
        node[newid].clear();
        node[newid].n = node[newid].inin = int(av[i].size()) - last;
        for(int k = last; k < av[i].size(); k++)
            inner[i][av[i][k]] = newid;
        newid++;
    }

    for(int i = 0; i < n; i++){
        int k = inner[ptx[i]][y[i]];
        if(ptx[i] && inner[ptx[i] - 1].find(y[i]) != inner[ptx[i] - 1].end())
            node[k].adj.pb(inner[ptx[i] - 1][y[i]]);
        if(ptx[i] + 1 < avx.size() && inner[ptx[i] + 1].find(y[i]) != inner[ptx[i] + 1].end())
            node[k].adj.pb(inner[ptx[i] + 1][y[i]]);
    }

    for(int i = 0; i < newid; i++)
        node[i].rebuild_adj();

    par[0] = -1;
    dfs_up(0);
    dfs_dw(0);
}

int DistanceSum(int n, int *x, int *y){

    solve(n, x, y);
    //cout << "here " << ans << endl;
    solve(n, y, x);
    //cout << "now " << ans << endl;
    ans /= 2;
    ans %= __int128(1e9);
    ll out = ans;
    return out;
}

Compilation message (stderr)

city.cpp: In function 'void solve(int, int*, int*)':
city.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i = 0; i < avx.size(); i++){
      |                    ~~^~~~~~~~~~~~
city.cpp:96:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int i = 0; i < avx.size(); i++){
      |                    ~~^~~~~~~~~~~~
city.cpp:99:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(int j = 1; j < av[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~
city.cpp:111:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for(int k = last; k < av[i].size(); k++)
      |                           ~~^~~~~~~~~~~~~~
city.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         if(ptx[i] + 1 < avx.size() && inner[ptx[i] + 1].find(y[i]) != inner[ptx[i] + 1].end())
      |            ~~~~~~~~~~~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 45 / 45