oj.uz

Submission #1112343

# Submission time Handle Problem Language Result Execution time Memory
1112343 2024-11-14T05:53:14 Z Sharky Road Construction (JOI21_road_construction) C++17
100 / 100
 6289 ms 68280 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 2.5e5 + 10;
int n, k;
array<int, 2> a[N];
map<int, vector<int>> mp;
vector<int> ans;

bool check(int di) {
    map<int, int> f;
    int cnt = 0, ptr = 1;
    for (int i = 1; i <= n; i++) {
        int x = a[i][0] - a[i][1], y = a[i][0] + a[i][1];
        while (ptr < i && a[ptr][0] - a[ptr][1] < x - di) {
            if (!--f[a[ptr][0] + a[ptr][1]]) f.erase(a[ptr][0] + a[ptr][1]);
            ptr++;
        }
        for (auto it = f.lower_bound(y - di); it != f.end() && it->first <= y + di; it++) {
            cnt += f[it->first];
            if (cnt >= k) return true;
        }
        f[y]++;
    }
    return false;
}

void out(int di) {
    map<int, vector<int>> f;
    int cnt = 0;
    int lb = -1e18, rb = -1e18;
    for (int i = 1; i <= n; i++) {
        int x = a[i][0] - a[i][1], y = a[i][0] + a[i][1];
        for (auto it = mp.lower_bound(lb); it != mp.end() && it->first < x - di; it++) {
            auto& ri = it->second;
            int lef = it->first;
            for (auto& v : ri) {
                f[v].erase(f[v].begin());
            }
        }
        for (auto it = mp.lower_bound(max(x - di, rb + 1)); it != mp.end() && it->first <= x; it++) {
            auto& ri = it->second;
            int lef = it->first;
            for (auto& v : ri) {
                f[v].push_back(lef);
            }
        }
        for (auto it = f.lower_bound(y-di); it != f.end() && it->first <= y + di; it++) {
            int lef = it->first;
            auto& ri = it->second;
            int sz = ri.size();
            if (lef == y) sz--;
            for (auto v : ri) {
                if (lef == y && v == x) continue;
                if (x == v && y > lef) continue;
                // cout << '(' << x << ',' << y << ')' << ' ' << '(' << v << ',' << it->first << ')' << '\n';
                cnt++;
                ans.push_back(max(abs(it->first - y), abs(v - x)));
                if (cnt >= k) return;
            }
        }
        lb = max(lb, x - di);
        rb = x;
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
        mp[a[i][0] - a[i][1]].push_back(a[i][0] + a[i][1]);
    }
    sort(a + 1, a + n + 1, [] (array<int, 2> x, array<int, 2> y) {
        if (x[0] - x[1] == y[0] - y[1]) return x[0] + x[1] < y[0] + y[1];
        return x[0] - x[1] < y[0] - y[1];
    });
    int l = 1, r = 4e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    out(l - 1);
    sort(ans.begin(), ans.end());
    while (ans.size() < k) ans.push_back(l);
    for (int i = 0; i < k; i++) cout << ans[i] << '\n';
    return 0;
}
/*
5 4
-2 2
-1 -1
2 0
2 2
2 -2
*/

Compilation message

road_construction.cpp: In function 'void out(long long int)':
road_construction.cpp:37:17: warning: unused variable 'lef' [-Wunused-variable]
   37 |             int lef = it->first;
      |                 ^~~
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:87:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   87 |     while (ans.size() < k) ans.push_back(l);
      |            ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 5396 KB Output is correct
2 Correct 161 ms 5332 KB Output is correct
3 Correct 138 ms 5580 KB Output is correct
4 Correct 132 ms 5352 KB Output is correct
5 Correct 154 ms 4320 KB Output is correct
6 Correct 3 ms 336 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 677 ms 64452 KB Output is correct
2 Correct 666 ms 62416 KB Output is correct
3 Correct 130 ms 5048 KB Output is correct
4 Correct 656 ms 62080 KB Output is correct
5 Correct 652 ms 62392 KB Output is correct
6 Correct 638 ms 62904 KB Output is correct
7 Correct 573 ms 61628 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 59588 KB Output is correct
2 Correct 670 ms 63304 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 455 ms 61996 KB Output is correct
5 Correct 288 ms 11600 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 59588 KB Output is correct
2 Correct 670 ms 63304 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 455 ms 61996 KB Output is correct
5 Correct 288 ms 11600 KB Output is correct
6 Correct 772 ms 62792 KB Output is correct
7 Correct 738 ms 62936 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 725 ms 59496 KB Output is correct
11 Correct 468 ms 61768 KB Output is correct
12 Correct 300 ms 12092 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 5396 KB Output is correct
2 Correct 161 ms 5332 KB Output is correct
3 Correct 138 ms 5580 KB Output is correct
4 Correct 132 ms 5352 KB Output is correct
5 Correct 154 ms 4320 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 1980 ms 30628 KB Output is correct
8 Correct 1961 ms 30512 KB Output is correct
9 Correct 140 ms 5324 KB Output is correct
10 Correct 673 ms 26936 KB Output is correct
11 Correct 410 ms 25624 KB Output is correct
12 Correct 233 ms 10168 KB Output is correct
13 Correct 369 ms 9284 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 5396 KB Output is correct
2 Correct 161 ms 5332 KB Output is correct
3 Correct 138 ms 5580 KB Output is correct
4 Correct 132 ms 5352 KB Output is correct
5 Correct 154 ms 4320 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 677 ms 64452 KB Output is correct
8 Correct 666 ms 62416 KB Output is correct
9 Correct 130 ms 5048 KB Output is correct
10 Correct 656 ms 62080 KB Output is correct
11 Correct 652 ms 62392 KB Output is correct
12 Correct 638 ms 62904 KB Output is correct
13 Correct 573 ms 61628 KB Output is correct
14 Correct 612 ms 59588 KB Output is correct
15 Correct 670 ms 63304 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 455 ms 61996 KB Output is correct
18 Correct 288 ms 11600 KB Output is correct
19 Correct 772 ms 62792 KB Output is correct
20 Correct 738 ms 62936 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 725 ms 59496 KB Output is correct
24 Correct 468 ms 61768 KB Output is correct
25 Correct 300 ms 12092 KB Output is correct
26 Correct 1980 ms 30628 KB Output is correct
27 Correct 1961 ms 30512 KB Output is correct
28 Correct 140 ms 5324 KB Output is correct
29 Correct 673 ms 26936 KB Output is correct
30 Correct 410 ms 25624 KB Output is correct
31 Correct 233 ms 10168 KB Output is correct
32 Correct 369 ms 9284 KB Output is correct
33 Correct 5782 ms 68068 KB Output is correct
34 Correct 6289 ms 68280 KB Output is correct
35 Correct 1415 ms 54164 KB Output is correct
36 Correct 415 ms 15764 KB Output is correct
37 Correct 461 ms 16056 KB Output is correct
38 Correct 505 ms 16516 KB Output is correct