제출 #1293678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1293678		BlockOG	Ideal city (IOI12_city)	C++20	23 / 100	81 ms	14196 KiB

city

#include <bits/stdc++.h>
using namespace std;

struct State {
    uint32_t sum = 0;
    uint32_t total_count = 0;
    vector<tuple<int32_t,int32_t,uint32_t>> ranges;

    State() {
        sum = 0;
        total_count = 0;
        ranges.clear();
    }

    void next_step(size_t n, const set<int32_t>& v) {
        total_count += (uint32_t)v.size();

        vector<tuple<int32_t,int32_t,uint32_t>> new_ranges;
        tuple<int32_t,int32_t,uint32_t> new_range = {-1, -1, 0};

        size_t j = 0;
        while (j < ranges.size() && get<0>(ranges[j]) == -1) j++;

        for (int32_t i : v) {
            if (i <= get<1>(new_range) + 1) {
                get<1>(new_range) = max(get<1>(new_range), i);
                get<2>(new_range) += 1;
            } else {
                if (get<0>(new_range) != -1) {
                    new_ranges.push_back(new_range);
                }
                new_range = {i, i, 1};
            }

            while (j < ranges.size() &&
                   get<0>(ranges[j]) <= get<1>(new_range) + 1) 
            {
                // trim left
                for (int k = get<0>(ranges[j]); k < get<1>(ranges[j]); k++) {
                    if (v.count(k)) {
                        get<0>(ranges[j]) = k;
                        break;
                    }
                }

                // trim right
                for (int k = get<1>(ranges[j]); k > get<0>(ranges[j]); k--) {
                    if (v.count(k)) {
                        get<1>(ranges[j]) = k;
                        break;
                    }
                }

                if (get<0>(ranges[j]) > get<1>(new_range) + 1)
                    break;

                if (get<0>(new_range) <= get<1>(ranges[j]) + 1) {
                    get<0>(new_range) = min(get<0>(new_range), get<0>(ranges[j]));
                    get<1>(new_range) = max(get<1>(new_range), get<1>(ranges[j]));
                    get<2>(new_range) += get<2>(ranges[j]);
                } else {
                    new_ranges.push_back(ranges[j]);
                }

                j++;
            }
        }

        if (get<0>(new_range) != -1)
            new_ranges.push_back(new_range);

        while (j < ranges.size() &&
               get<0>(ranges[j]) <= get<1>(new_range) + 1)
        {
            for (int k = get<0>(ranges[j]); k < get<1>(ranges[j]); k++) {
                if (v.count(k)) {
                    get<0>(ranges[j]) = k;
                    break;
                }
            }
            for (int k = get<1>(ranges[j]); k > get<0>(ranges[j]); k--) {
                if (v.count(k)) {
                    get<1>(ranges[j]) = k;
                    break;
                }
            }
            new_ranges.push_back(ranges[j]);
            j++;
        }

        ranges = move(new_ranges);

        uint64_t curr_sum =
            (uint64_t)total_count * ((uint64_t)n + total_count);

        for (auto &r : ranges) {
            uint64_t x = get<2>(r);
            curr_sum -= 2 * x * x;
        }

        sum = (sum + (curr_sum % 1000000000ULL)) % 1000000000ULL;
    }
};


uint32_t solve(const vector<pair<int32_t,int32_t>>& input) {
    map<int32_t, set<int32_t>> x_to_y, y_to_x;
    for (auto &[x, y] : input) {
        x_to_y[x].insert(y);
        y_to_x[y].insert(x);
    }

    uint64_t res = 0;

    // horizontal
    {
        uint64_t res_horiz = 0;

        {
            State s;
            for (auto &p : x_to_y)
                s.next_step(input.size(), p.second);
            res_horiz += s.sum;
        }
        {
            State s;
            for (auto it = x_to_y.rbegin(); it != x_to_y.rend(); ++it)
                s.next_step(input.size(), it->second);
            res_horiz += s.sum;
        }

        res = (res + (res_horiz / 2) % 1000000000ULL) % 1000000000ULL;
    }

    // vertical
    {
        uint64_t res_vert = 0;

        {
            State s;
            for (auto &p : y_to_x)
                s.next_step(input.size(), p.second);
            res_vert += s.sum;
        }
        {
            State s;
            for (auto it = y_to_x.rbegin(); it != y_to_x.rend(); ++it)
                s.next_step(input.size(), it->second);
            res_vert += s.sum;
        }

        res = (res + (res_vert / 2) % 1000000000ULL) % 1000000000ULL;
    }

    return res % 1000000000ULL;
}

int DistanceSum(int n, int x[], int y[]) {
    vector<pair<int32_t, int32_t>> input;
    for (int i = 0; i < n; i++) input.push_back({x[i], y[i]});
    return solve(input);
}

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