oj.uz

Submission #1112079

# Submission time Handle Problem Language Result Execution time Memory
1112079 2024-11-13T16:08:36 Z Sharky Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 62280 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, bool add) {
    // cout << "exh: " << di << '\n';
    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());
                // cout << v << " erase " << it->first << '\n';
            }
        }
        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);
                // cout << v << " insert " << it->first << '\n';
            }
        }
        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--;
            // cout << x << ' ' << y << ' ' << it->first << ' ' << sz << '\n';
            // int ex = min(sz, k - cnt);
            // cnt += ex;
            // if (add) {
                for (auto v : ri) {
                    if (lef == y && v == x) continue;
                    if (x == v && y > lef) continue;
                    // cout << '(' << x << ',' << y << ')' << ' ' << '(' << v << ',' << it->first << ')' << '\n';
                    cnt++;
                    if (add) ans.push_back(max(abs(it->first - y), abs(v - x)));
                    if (cnt >= k) return true;
                    // if (ans.size() >= k) return true;
                }
            // }
            if (cnt >= k) {
                // cout << "true!\n";
                return true;
            }
        }
        lb = max(lb, x - di);
        rb = x;
    }
    // cout << "false!\n";
    return false;
}

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) {
        return x[0] - x[1] < y[0] - y[1];
    });
    for (auto& [st, v] : mp) sort(v.begin(), v.end());
    int l = 1, r = 5e9;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (check(mid, 0)) r = mid;
        else l = mid + 1;
    }
    // cout << "var: " << l-1 << '\n';
    check(l-1, 1);
    // for (auto x : ans) cout << x << ' ';
    // cout << '\n';
    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 'bool check(long long int, bool)':
road_construction.cpp:20:17: warning: unused variable 'lef' [-Wunused-variable]
   20 |             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 153 ms 5304 KB Output is correct
2 Correct 144 ms 5300 KB Output is correct
3 Correct 102 ms 5476 KB Output is correct
4 Correct 110 ms 5324 KB Output is correct
5 Correct 102 ms 4280 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 3325 ms 62228 KB Output is correct
2 Correct 3306 ms 62280 KB Output is correct
3 Correct 95 ms 5304 KB Output is correct
4 Correct 2712 ms 62200 KB Output is correct
5 Correct 2679 ms 62224 KB Output is correct
6 Correct 2478 ms 62224 KB Output is correct
7 Correct 1630 ms 61472 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2553 ms 59156 KB Output is correct
2 Correct 4922 ms 59152 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1659 ms 59132 KB Output is correct
5 Correct 743 ms 7520 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2553 ms 59156 KB Output is correct
2 Correct 4922 ms 59152 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1659 ms 59132 KB Output is correct
5 Correct 743 ms 7520 KB Output is correct
6 Correct 6135 ms 59152 KB Output is correct
7 Correct 5549 ms 59152 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 5875 ms 54876 KB Output is correct
11 Correct 1677 ms 59156 KB Output is correct
12 Correct 789 ms 7528 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 5304 KB Output is correct
2 Correct 144 ms 5300 KB Output is correct
3 Correct 102 ms 5476 KB Output is correct
4 Correct 110 ms 5324 KB Output is correct
5 Correct 102 ms 4280 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Execution timed out 10040 ms 24392 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 5304 KB Output is correct
2 Correct 144 ms 5300 KB Output is correct
3 Correct 102 ms 5476 KB Output is correct
4 Correct 110 ms 5324 KB Output is correct
5 Correct 102 ms 4280 KB Output is correct
6 Correct 3 ms 336 KB Output is correct
7 Correct 3325 ms 62228 KB Output is correct
8 Correct 3306 ms 62280 KB Output is correct
9 Correct 95 ms 5304 KB Output is correct
10 Correct 2712 ms 62200 KB Output is correct
11 Correct 2679 ms 62224 KB Output is correct
12 Correct 2478 ms 62224 KB Output is correct
13 Correct 1630 ms 61472 KB Output is correct
14 Correct 2553 ms 59156 KB Output is correct
15 Correct 4922 ms 59152 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1659 ms 59132 KB Output is correct
18 Correct 743 ms 7520 KB Output is correct
19 Correct 6135 ms 59152 KB Output is correct
20 Correct 5549 ms 59152 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 5875 ms 54876 KB Output is correct
24 Correct 1677 ms 59156 KB Output is correct
25 Correct 789 ms 7528 KB Output is correct
26 Execution timed out 10040 ms 24392 KB Time limit exceeded
27 Halted 0 ms 0 KB -