Submission #1293662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293662		BlockOG	Ideal city (IOI12_city)	C++20	23 / 100	70 ms	13560 KiB

city

#include <bits/stdc++.h>

// meeeooowwwww mrrowwww :3
// go play vivid/stasis!! now!!!! 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;
}();

map<int, set<int>> x_to_y;
map<int, set<int>> y_to_x;

struct State {
    int sum = 0, total_count = 0;
    vector<pair<pair<int, int>, int>> ranges;

    void next(int n, const set<int> &v) {
        total_count += v.size();

        vector<pair<pair<int, int>, int>> new_ranges;
        pair<pair<int, int>, int> new_range = {{-1, -1}, -1};
        int j = 0;
        for (int i : v) {
            if (i <= new_range.f.s + 1) new_range.f.s = max(new_range.f.s, i), new_range.s++;
            else {
                if (new_range.f.f != -1) new_ranges.pb(new_range);
                new_range = {{i, i}, 1};
            }
            
            for (; j < ranges.size() && ranges[j].f.f <= new_range.f.s + 1; j++) {
                fo(k, ranges[j].f.f, ranges[j].f.s)
                    if (v.count(k)) {
                        ranges[j].f.f = k;
                        break;
                    }
                of(k, ranges[j].f.f + 1, ranges[j].f.s + 1)
                    if (v.count(k)) {
                        ranges[j].f.s = k;
                        break;
                    }

                if (ranges[j].f.f > new_range.f.s + 1) break;
                    
                if (new_range.f.f <= ranges[j].f.s + 1) new_range.f.f = min(new_range.f.f, ranges[j].f.f), new_range.f.s = max(new_range.f.s, ranges[j].f.s), new_range.s += ranges[j].s;
                else {
                    new_ranges.pb(ranges[j]);
                }
            }
        }

        if (new_range.f.f != -1) new_ranges.pb(new_range);
        for (; j < ranges.size(); j++) {
            fo(k, ranges[j].f.f, ranges[j].f.s)
                if (v.count(k)) {
                    ranges[j].f.f = k;
                    break;
                }
            of(k, ranges[j].f.f + 1, ranges[j].f.s + 1)
                if (v.count(k)) {
                    ranges[j].f.s = k;
                    break;
                }

            new_ranges.pb(ranges[j]);
        }
        ranges = new_ranges;

        long long curr_sum = (long long)total_count * (n + total_count);
        for (auto [_, i] : ranges) curr_sum -= 2 * (long long)i*i;
        sum = (sum + curr_sum % 1000000000) % 1000000000;
    }
};

int DistanceSum(int n, int x[], int y[]) {
    fo(i, 0, n) x_to_y[x[i]].insert(y[i]);
    fo(i, 0, n) y_to_x[y[i]].insert(x[i]);

    int res = 0;
    {
        int res_horiz = 0;
        {
            State s;
            for (auto it = x_to_y.begin(); it != x_to_y.end(); it++) s.next(n, it->s);
            res_horiz += s.sum;
        }
        {
            State s;
            for (auto it = x_to_y.rbegin(); it != x_to_y.rend(); it++) s.next(n, it->s);
            res_horiz += s.sum;
        }

        res += res_horiz / 2 % 1000000000;
    }
    {
        int res_vert = 0;
        {
            State s;
            for (auto it = y_to_x.begin(); it != y_to_x.end(); it++) s.next(n, it->s);
            res_vert += s.sum;
        }
        {
            State s;
            for (auto it = y_to_x.rbegin(); it != y_to_x.rend(); it++) s.next(n, it->s);
            res_vert += s.sum;
        }

        res += res_vert / 2 % 1000000000;
    }

    return res % 1000000000;
}

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