oj.uz

Submission #873220

# Submission time Handle Problem Language Result Execution time Memory
873220 2023-11-14T16:31:14 Z boris_mihov Road Construction (JOI21_road_construction) C++17
5 / 100
 10000 ms 91800 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

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

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

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

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

        llong lPtr = 0, rPtr = 0;
        for (llong 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++]);
            }
        }
    }

    llong binary(llong node, llong value)
    {
        llong 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;
    }

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

        llong res = 0;
        llong 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);
    }

    llong leftSearch(llong value)
    {
        llong 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;
    }

    llong rightSearch(llong value)
    {
        llong 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;
    }

    llong query(Pollong p, llong len)
    {
        llong qL = leftSearch(p.x - len);
        llong 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,llong> searchNext(Pollong p, llong 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
{
    llong idx;
    llong dist;
    llong count;
    llong sum;

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

llong nums[MAXN];
std::vector <llong> answer;
std::priority_queue <Element> pq;
void solve()
{
    for (llong 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 (llong i = 1 ; i <= n ; ++i)
    {
        nums[i] = p[i].y;
    }

    tree.build(nums);
    for (llong 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 (llong 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 (llong i = n ; i < k ; i += 2)
    {
        std::cout << answer[i] << '\n';
    }
}

void input()
{
    std::cin >> n >> k;
    for (llong 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);
}

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

    return 0;
}

Compilation message

road_construction.cpp: In member function 'void MST::build(llong, llong, llong, llong*)':
road_construction.cpp:42:22: warning: comparison of integer expressions of different signedness: 'llong' {aka 'long long 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: 'llong' {aka 'long long 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<long long int>::size_type' {aka 'long unsigned int'} and 'llong' {aka 'long long int'} [-Wsign-compare]
  181 |     while (answer.size() < k)
      |            ~~~~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5777 ms 33996 KB Output is correct
2 Correct 5770 ms 34104 KB Output is correct
3 Correct 4430 ms 33800 KB Output is correct
4 Correct 3536 ms 33848 KB Output is correct
5 Correct 5154 ms 32936 KB Output is correct
6 Correct 21 ms 27224 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10080 ms 91800 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10042 ms 86448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10042 ms 86448 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5777 ms 33996 KB Output is correct
2 Correct 5770 ms 34104 KB Output is correct
3 Correct 4430 ms 33800 KB Output is correct
4 Correct 3536 ms 33848 KB Output is correct
5 Correct 5154 ms 32936 KB Output is correct
6 Correct 21 ms 27224 KB Output is correct
7 Execution timed out 10086 ms 60416 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5777 ms 33996 KB Output is correct
2 Correct 5770 ms 34104 KB Output is correct
3 Correct 4430 ms 33800 KB Output is correct
4 Correct 3536 ms 33848 KB Output is correct
5 Correct 5154 ms 32936 KB Output is correct
6 Correct 21 ms 27224 KB Output is correct
7 Execution timed out 10080 ms 91800 KB Time limit exceeded
8 Halted 0 ms 0 KB -