Submission #1294044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294044		BlockOG	Ideal city (IOI12_city)	C++20	100 / 100	43 ms	11172 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;

static int id_counter = 0;
struct Node {
    int id;
    int size;
    vector<shared_ptr<Node>> children;

    pair<int, int> get(int n, int p=-1) {
        int total_size = size;
        long long res = 0;

        for (const shared_ptr<Node> child : children) {
            if (child->id == p) continue;
            auto [child_total_size, child_res] = child->get(n, id);
            total_size += child_total_size;
            res += child_res;
        }

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

shared_ptr<Node> get_tree(vector<pair<int, int>> &cells) {
    shared_ptr<Node> root;

    vector<pair<pair<int, int>, shared_ptr<Node>>> 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>, shared_ptr<Node>>> 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;
            shared_ptr<Node> node = make_shared<Node>(Node { .id = id_counter++, .size = k - l });
            if (!root) root = node;
            new_ranges.pb({{start, end}, node});

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

        ranges = new_ranges;
    }
    
    return root;
}

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_tree(cells_x_y)->get(n).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_tree(cells_y_x)->get(n).s;
    }

    return res % MOD;
}

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