oj.uz

Submission #825895

# Submission time Handle Problem Language Result Execution time Memory
825895 2023-08-15T09:08:12 Z xink Road Construction (JOI21_road_construction) C++14
100 / 100
 1827 ms 18252 KB 
#include <iostream>
#include <vector>
#include <utility>
#include <sstream>
#include <climits>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <assert.h>
#include <set>
#define ll long long
#define ld long double
using namespace std;
const ll mod = 1e9 + 7;
typedef vector<int> vi;
typedef pair<ll, ll> ii;
typedef pair<ii, int> pii;
typedef vector<ii> vii;
const int maxn1 = 3e5 + 5, maxn2 = 1e6 + 6;
ii coor[maxn1];
ll dist[maxn2];
struct cmp
{
    bool operator()(const ii &a, const ii &b) const
    {
        if (a.second == b.second)
            return a.first < b.first;
        return a.second < b.second;
    }
};

set<ii, cmp> s;

ll get_manhattan_dist(int i, int j)
{
    return abs(coor[i].first - coor[j].first) + abs(coor[i].second - coor[j].second);
}

ll get_manhattan_dist(ii p1, ii p2)
{
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}

void solve_sub1(int n, int k)
{
    int n_road = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++)
        {
            dist[n_road++] = get_manhattan_dist(i, j);
        }
    }
    sort(dist, dist + n_road);
    for (int i = 0; i < k; i++)
    {
        cout << dist[i] << "\n";
    }
}

void solve_sub2(int n, ll k)
{
    sort(coor, coor + n);
    ll l = 1, r = coor[n - 1].first - coor[0].first;
    while (l < r)
    {
        int m = (l + r) >> 1, l1 = 0;
        ll cnt = 0;
        for (int i = 0; i < n; i++)
        {
            while (l1 < i && get_manhattan_dist(l1, i) > m)
            {
                l1++;
            }
            cnt += i - l1;
        }
        if (cnt >= k)
        {
            r = m;
        }
        else
        {
            l = m + 1;
        }
    }
    int n_road = 0, lp = 0;
    for (int i = 0; i < n; i++)
    {
        while (lp < i && get_manhattan_dist(lp, i) >= l)
        {
            lp++;
        }
        for (int j = lp; j < i; j++)
        {
            dist[n_road++] = get_manhattan_dist(j, i);
        }
    }
    for (int i = n_road; i < k; i++)
    {
        dist[i] = l;
    }
    sort(dist, dist + k);
    for (int i = 0; i < k; i++)
    {
        cout << dist[i] << '\n';
    }
}

bool check_enough(int n, ll k, ll m)
{
    s.clear();
    ll cnt = 0;
    for (int i = 0; i < n; i++)
    {
        ii curr_p = {-1e10, coor[i].second - m};
        while (true)
        {
            set<ii>::iterator it1 = s.upper_bound(curr_p);
            if (it1 == s.end())
                break;
            curr_p = *it1;
            if (curr_p.second > coor[i].second + m)
                break;

            if (curr_p.first < coor[i].first - m)
            {
                s.erase(it1);
                continue;
            }

            if (get_manhattan_dist(curr_p, coor[i]) <= m)
            {
                cnt++;
                if (cnt >= k)
                    return true;
            }
        }
        s.insert(coor[i]);
    }
    return false;
}

void create_dist(int n, ll k, ll l)
{
    s.clear();
    ll n_road = 0;
    for (int i = 0; i < n; i++)
    {
        ii curr_p = {-1e10, coor[i].second - l};
        while (true)
        {
            set<ii>::iterator it1 = s.upper_bound(curr_p);
            if (it1 == s.end())
                break;
            curr_p = *it1;
            if (curr_p.second > coor[i].second + l)
                break;

            if (curr_p.first < coor[i].first - l)
            {
                s.erase(it1);
                continue;
            }

            if (get_manhattan_dist(curr_p, coor[i]) < l)
            {
                dist[n_road++] = get_manhattan_dist(curr_p, coor[i]);
            }
        }
        s.insert(coor[i]);
    }
    for (int i = n_road; i < k; i++)
    {
        dist[i] = l;
    }
    sort(dist, dist + k);
    for (int i = 0; i < k; i++)
    {
        cout << dist[i] << "\n";
    }
}

void solve_sub3(int n, int k)
{
    sort(coor, coor + n);
    ll l = 1, r = 1e10;
    while (l < r)
    {
        int m = (l + r) >> 1;
        if (check_enough(n, k, m))
        {
            r = m;
        }
        else
        {
            l = m + 1;
        }
    }
    create_dist(n, k, l);
}

void solve()
{
    int n, k;
    cin >> n >> k;
    bool all_y0 = 1;
    for (int i = 0; i < n; i++)
    {
        cin >> coor[i].first >> coor[i].second;
        all_y0 &= (coor[i].second == 0);
    }
    if (n <= 1000)
    {
        solve_sub1(n, k);
        return;
    }
    if (all_y0)
    {
        solve_sub2(n, k);
        return;
    }
    solve_sub3(n, k);
}

int main()
{
    // freopen("input_text", "r", stdin);
    // freopen("output_text", "w", stdout);
    // ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t-- > 0)
        solve();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6732 KB Output is correct
2 Correct 52 ms 6708 KB Output is correct
3 Correct 34 ms 4820 KB Output is correct
4 Correct 34 ms 4976 KB Output is correct
5 Correct 49 ms 5664 KB Output is correct
6 Correct 16 ms 4180 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 224 ms 7372 KB Output is correct
2 Correct 221 ms 7276 KB Output is correct
3 Correct 40 ms 4684 KB Output is correct
4 Correct 203 ms 10184 KB Output is correct
5 Correct 150 ms 10352 KB Output is correct
6 Correct 158 ms 10444 KB Output is correct
7 Correct 158 ms 9788 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 12828 KB Output is correct
2 Correct 1194 ms 9640 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 139 ms 7092 KB Output is correct
5 Correct 564 ms 9580 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 12828 KB Output is correct
2 Correct 1194 ms 9640 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 139 ms 7092 KB Output is correct
5 Correct 564 ms 9580 KB Output is correct
6 Correct 1296 ms 12196 KB Output is correct
7 Correct 1173 ms 12292 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1465 ms 18252 KB Output is correct
11 Correct 134 ms 7128 KB Output is correct
12 Correct 613 ms 9576 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6732 KB Output is correct
2 Correct 52 ms 6708 KB Output is correct
3 Correct 34 ms 4820 KB Output is correct
4 Correct 34 ms 4976 KB Output is correct
5 Correct 49 ms 5664 KB Output is correct
6 Correct 16 ms 4180 KB Output is correct
7 Correct 1062 ms 7904 KB Output is correct
8 Correct 1034 ms 8028 KB Output is correct
9 Correct 34 ms 4868 KB Output is correct
10 Correct 744 ms 7284 KB Output is correct
11 Correct 882 ms 11320 KB Output is correct
12 Correct 523 ms 7928 KB Output is correct
13 Correct 591 ms 6604 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 6732 KB Output is correct
2 Correct 52 ms 6708 KB Output is correct
3 Correct 34 ms 4820 KB Output is correct
4 Correct 34 ms 4976 KB Output is correct
5 Correct 49 ms 5664 KB Output is correct
6 Correct 16 ms 4180 KB Output is correct
7 Correct 224 ms 7372 KB Output is correct
8 Correct 221 ms 7276 KB Output is correct
9 Correct 40 ms 4684 KB Output is correct
10 Correct 203 ms 10184 KB Output is correct
11 Correct 150 ms 10352 KB Output is correct
12 Correct 158 ms 10444 KB Output is correct
13 Correct 158 ms 9788 KB Output is correct
14 Correct 643 ms 12828 KB Output is correct
15 Correct 1194 ms 9640 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 139 ms 7092 KB Output is correct
18 Correct 564 ms 9580 KB Output is correct
19 Correct 1296 ms 12196 KB Output is correct
20 Correct 1173 ms 12292 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 304 KB Output is correct
23 Correct 1465 ms 18252 KB Output is correct
24 Correct 134 ms 7128 KB Output is correct
25 Correct 613 ms 9576 KB Output is correct
26 Correct 1062 ms 7904 KB Output is correct
27 Correct 1034 ms 8028 KB Output is correct
28 Correct 34 ms 4868 KB Output is correct
29 Correct 744 ms 7284 KB Output is correct
30 Correct 882 ms 11320 KB Output is correct
31 Correct 523 ms 7928 KB Output is correct
32 Correct 591 ms 6604 KB Output is correct
33 Correct 1820 ms 13376 KB Output is correct
34 Correct 1827 ms 13412 KB Output is correct
35 Correct 1752 ms 13288 KB Output is correct
36 Correct 898 ms 13388 KB Output is correct
37 Correct 791 ms 13352 KB Output is correct
38 Correct 863 ms 12208 KB Output is correct