Submission #873217

#	Time	Username	Problem	Language	Result	Execution time	Memory
873217		boris_mihov	Road Construction (JOI21_road_construction)	C++17	0 / 100	10036 ms	88876 KiB

road_construction

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 250000 + 10;
const llong INF = 4e9 + 1;

int n, k;
struct Point
{
    llong x, y;
    friend bool operator < (const Point &a, const Point &b)
    {
        return a.x < b.x || (a.x == b.x && a.y < b.y);
    }
};

Point p[MAXN];
struct MST
{
    std::vector <llong> tree[4 * MAXN];
    void build(int l, int r, int node, llong nums[])
    {
        if (l == r)
        {
            tree[node].push_back(nums[l]);
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, nums);
        build(mid + 1, r, 2*node + 1, nums);
        tree[node].reserve(r - l + 1);

        int lPtr = 0, rPtr = 0;
        for (int i = l ; i <= r ; ++i)
        {
            if (lPtr == tree[2*node].size())
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
                continue;
            }

            if (rPtr == tree[2*node + 1].size())
            {
                tree[node].push_back(tree[2*node][lPtr++]);
                continue;
            }

            if (tree[2*node][lPtr] < tree[2*node + 1][rPtr])
            {
                tree[node].push_back(tree[2*node][lPtr++]);
            } else
            {
                tree[node].push_back(tree[2*node + 1][rPtr++]);
            }
        }
    }

    int binary(int node, llong value)
    {
        int l = -1, r = tree[node].size(), mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree[node][mid] <= value) l = mid;
            else r = mid;
        }

        return r;
    }

    int query(int l, int r, int node, int queryL, int queryR, llong queryValL, llong queryValR)
    {
        if (queryL <= l && r <= queryR)
        {
            return binary(node, queryValR) - binary(node, queryValL - 1);
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR, queryValL, queryValR);
        if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR, queryValL, queryValR);
        return res;
    }

    void build(llong nums[])
    {
        build(1, n, 1, nums);
    }

    int leftSearch(llong value)
    {
        int l = 0, r = n + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (p[mid].x < value) l = mid;
            else r = mid;
        }

        return r;
    }

    int rightSearch(llong value)
    {
        int l = 0, r = n + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (p[mid].x <= value) l = mid;
            else r = mid;
        }

        return l;
    }

    int query(Point p, llong len)
    {
        int qL = leftSearch(p.x - len);
        int qR = rightSearch(p.x + len);
        if (qL > qR) return 0;
        return query(1, n, 1, qL, qR, p.y - len, p.y + len);
    }

    std::pair <llong,int> searchNext(Point p, int currReach, llong minDist)
    {
        llong l = minDist - 1, r = INF, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (query(p, mid) == currReach) l = mid;
            else r = mid;
        }

        return {r, query(p, r) - currReach};
    }
};  

MST tree;
struct Element
{
    int idx;
    llong dist;
    int count;
    int sum;

    friend bool operator < (const Element &a, const Element &b)
    {
        return a.dist > b.dist;
    }
};

llong nums[MAXN];
std::vector <int> answer;
std::priority_queue <Element> pq;
void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        p[i] = {p[i].x - p[i].y, p[i].x + p[i].y};
    }

    std::sort(p + 1, p + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        nums[i] = p[i].y;
    }

    tree.build(nums);
    for (int i = 1 ; i <= n ; ++i)
    {
        auto [to, cnt] = tree.searchNext(p[i], 0, 0);
        pq.push({i, to, cnt, cnt});
    }

    while (answer.size() < k)
    {
        auto [idx, dist, count, sum] = pq.top();
        pq.pop();

        for (int i = 0 ; i < count ; ++i)
        {
            answer.push_back(dist);
        }

        auto [to, cnt] = tree.searchNext(p[idx], sum, dist + 1);
        if (to < INF) pq.push({idx, to, cnt, sum + cnt});
    }

    for (int i = n ; i < k ; i += 2)
    {
        std::cout << answer[i] << '\n';
    }
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> p[i].x >> p[i].y;
    }

    k = 2 * k + n;
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

Compilation message (stderr)

road_construction.cpp: In member function 'void MST::build(int, int, int, llong*)':
road_construction.cpp:42:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if (lPtr == tree[2*node].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |             if (rPtr == tree[2*node + 1].size())
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp: In function 'void solve()':
road_construction.cpp:181:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  181 |     while (answer.size() < k)
      |            ~~~~~~~~~~~~~~^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35