Submission #1294045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294045		BlockOG	Ideal city (IOI12_city)	C++20	100 / 100	39 ms	6308 KiB

city

#include <bits/stdc++.h>

// mrrrowwww meeowwwww :3
// go play vivid/stasis! !! !!! https://vividstasis.gay

#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;

int ____init = []{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    return 0;
}();

const int MOD = 1000000000;

struct Node {
    int size;
    vector<int> adj;
};

pair<int, int> get(const vector<Node> &tree, int n, int i, int p=-1) {
    int total_size = tree[i].size;
    long long res = 0;

    for (int j : tree[i].adj) {
        if (j == p) continue;
        auto [child_total_size, child_res] = get(tree, n, j, i);
        total_size += child_total_size;
        res += child_res;
    }

    res += (long long) total_size * (n - total_size);
    return {total_size, res % MOD};
}

vector<Node> get_tree(vector<pair<int, int>> &cells) {
    vector<Node> tree;
    
    vector<pair<pair<int, int>, int>> ranges;
    for (int i = 0, j = 0; i < cells.size(); j = i) {
        for (i++; i < cells.size() && cells[i].f == cells[j].f; i++);

        vector<pair<pair<int, int>, int>> new_ranges;
        for (int k = j, l = j, m = 0; k < i; l = k) {
            for (k++; k < i && cells[k].s == cells[k - 1].s + 1; k++);

            int start = cells[l].s, end = cells[k - 1].s;
            int node = tree.size(); tree.pb({ .size = k - l });
            new_ranges.pb({{start, end}, node});

            for (; m < ranges.size() && ranges[m].f.f <= end; m++) {
                if (ranges[m].f.s >= start) {
                    tree[ranges[m].s].adj.pb(node);
                    tree[node].adj.pb(ranges[m].s);
                }
            }
            if (m) m--;
        }

        ranges = new_ranges;
    }
    
    return tree;
}

int DistanceSum(int n, int x[], int y[]) {
    int res = 0;

    {
        vector<pair<int, int>> cells_x_y;
        fo(i, 0, n) cells_x_y.pb({x[i], y[i]});
        sort(be(cells_x_y));
        res += get(get_tree(cells_x_y), n, 0).s;
    }
    {
        vector<pair<int, int>> cells_y_x;
        fo(i, 0, n) cells_y_x.pb({y[i], x[i]});
        sort(be(cells_y_x));
        res += get(get_tree(cells_y_x), n, 0).s;
    }

    return res % MOD;
}

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