Submission #1214769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214769		LIA	Ideal city (IOI12_city)	C++17	100 / 100	75 ms	15656 KiB

city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple <ll,ll,ll> plll;
typedef vector <plll> vplll;
typedef pair <ll,ll> pll;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <vector <pll>> vvpll;
typedef vector <vector <ll>> vvll;
typedef vector <bool> vb;
typedef vector <vector <bool>> vvb;
#define loop(i, s, e) for (ll i = (s); i < (e); ++i)
#define loopr(i, e, s) for (ll i = (e)-1; i >= (s); --i)
#define all(a) a.begin(), a.end()
const ll inf = 1e9 + 7;
const ll mod =  1e9;

vvll gh, gv;
vll wh, wv;
vll sh, sv;
ll th, tv, n, res;

ll dfsh(ll u, ll p) {
    ll s = wh[u];
    for (ll v : gh[u]) if (v != p) s += dfsh(v, u);
    sh[u] = s;
    if (p != -1) res = (res + (s * (th - s)) % mod) % mod;
    return s;
}

ll dfsv(ll u, ll p) {
    ll s = wv[u];
    for (ll v : gv[u]) if (v != p) s += dfsv(v, u);
    sv[u] = s;
    if (p != -1) res = (res + (s * (tv - s)) % mod) % mod;
    return s;
}

int DistanceSum(int nn, int *x, int *y) {
    res = 0;
    n = nn;
    map<ll, vector<pair<ll,int>>> rw, cw;
    loop(i,0,n) {
        rw[x[i]].push_back({y[i],i});
        cw[y[i]].push_back({x[i],i});
    }
    int hc = 0, vc = 0;
    vector<int> ih(n), iv(n);
    vector<ll> hl, hh, vl, vh;
    wh.clear(); wv.clear();
    map<ll, vector<int>> rseg, cseg;
    for (auto &pr : rw) {
        auto &v = pr.second; sort(all(v));
        int sz = v.size(), st = 0;
        loop(i,1,sz+1) {
            if (i == sz || v[i].first != v[i-1].first+1) {
                hl.push_back(v[st].first);
                hh.push_back(v[i-1].first);
                ll cnt = i - st;
                wh.push_back(cnt);
                rseg[pr.first].push_back(hc);
                loop(j,st,i) ih[v[j].second] = hc;
                hc++;
                st = i;
            }
        }
    }
    for (auto &pc : cw) {
        auto &v = pc.second; sort(all(v));
        int sz = v.size(), st = 0;
        loop(i,1,sz+1) {
            if (i == sz || v[i].first != v[i-1].first+1) {
                vl.push_back(v[st].first);
                vh.push_back(v[i-1].first);
                ll cnt = i - st;
                wv.push_back(cnt);
                cseg[pc.first].push_back(vc);
                loop(j,st,i) iv[v[j].second] = vc;
                vc++;
                st = i;
            }
        }
    }
    gh.assign(hc, vll());
    for (auto it = rseg.begin(); it != rseg.end(); ++it) {
        auto jt = next(it);
        if (jt != rseg.end() && jt->first == it->first+1) {
            auto &uL = it->second, &vL = jt->second;
            int i1 = 0, j1 = 0;
            while (i1 < (int)uL.size() && j1 < (int)vL.size()) {
                int u = uL[i1], v = vL[j1];
                if (hh[u] < hl[v]) i1++;
                else if (hh[v] < hl[u]) j1++;
                else {
                    gh[u].push_back(v);
                    gh[v].push_back(u);
                    if (hh[u] < hh[v]) i1++;
                    else j1++;
                }
            }
        }
    }
    gv.assign(vc, vll());
    for (auto it = cseg.begin(); it != cseg.end(); ++it) {
        auto jt = next(it);
        if (jt != cseg.end() && jt->first == it->first+1) {
            auto &uL = it->second, &vL = jt->second;
            int i1 = 0, j1 = 0;
            while (i1 < (int)uL.size() && j1 < (int)vL.size()) {
                int u = uL[i1], v = vL[j1];
                if (vh[u] < vl[v]) i1++;
                else if (vh[v] < vl[u]) j1++;
                else {
                    gv[u].push_back(v);
                    gv[v].push_back(u);
                    if (vh[u] < vh[v]) i1++;
                    else j1++;
                }
            }
        }
    }
    th = 0; loop(i,0,hc) th += wh[i];
    sh.assign(hc,0);
    if (hc > 0) dfsh(0, -1);
    tv = 0; loop(i,0,vc) tv += wv[i];
    sv.assign(vc,0);
    if (vc > 0) dfsv(0, -1);
    return res;
}

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