oj.uz

Submission #1112067

# Submission time Handle Problem Language Result Execution time Memory
1112067 2024-11-13T15:55:29 Z Sharky Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 58440 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, set<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++) {
            for (auto& v : it->second) {
                f[v].erase(it->first);
                // cout << v << " erase " << it->first << '\n';
            }
        }
        for (auto it = mp.lower_bound(max(x - di, rb + 1)); it != mp.end() && it->first <= x; it++) {
            for (auto& v : it->second) {
                f[v].insert(it->first);
                // cout << v << " insert " << it->first << '\n';
            }
        }
        for (auto it = f.lower_bound(y-di); it != f.end() && it->first <= y + di; it++) {
            int sz = f[it->first].size();
            if (it->first == y) sz--;
            // cout << x << ' ' << y << ' ' << it->first << ' ' << sz << '\n';
            // int ex = min(sz, k - cnt);
            // cnt += ex;
            // if (add) {
                for (auto& v : f[it->first]) {
                    if (it->first == y && v == x) continue;
                    if (x == v && y > it->first) 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 'int32_t main()':
road_construction.cpp:81: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]
   81 |     while (ans.size() < k) ans.push_back(l);
      |            ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 5560 KB Output is correct
2 Correct 491 ms 5304 KB Output is correct
3 Correct 305 ms 5324 KB Output is correct
4 Correct 283 ms 5320 KB Output is correct
5 Correct 366 ms 4172 KB Output is correct
6 Correct 4 ms 336 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4292 ms 58344 KB Output is correct
2 Correct 4453 ms 58440 KB Output is correct
3 Correct 271 ms 5180 KB Output is correct
4 Correct 3922 ms 58332 KB Output is correct
5 Correct 3703 ms 58344 KB Output is correct
6 Correct 3379 ms 58440 KB Output is correct
7 Correct 2653 ms 57588 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2785 ms 55232 KB Output is correct
2 Correct 5509 ms 55236 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1828 ms 55236 KB Output is correct
5 Correct 1111 ms 7496 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2785 ms 55232 KB Output is correct
2 Correct 5509 ms 55236 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1828 ms 55236 KB Output is correct
5 Correct 1111 ms 7496 KB Output is correct
6 Correct 7356 ms 55236 KB Output is correct
7 Correct 6346 ms 55244 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 6229 ms 56348 KB Output is correct
11 Correct 1841 ms 57912 KB Output is correct
12 Correct 1051 ms 12148 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 5560 KB Output is correct
2 Correct 491 ms 5304 KB Output is correct
3 Correct 305 ms 5324 KB Output is correct
4 Correct 283 ms 5320 KB Output is correct
5 Correct 366 ms 4172 KB Output is correct
6 Correct 4 ms 336 KB Output is correct
7 Execution timed out 10057 ms 24880 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 512 ms 5560 KB Output is correct
2 Correct 491 ms 5304 KB Output is correct
3 Correct 305 ms 5324 KB Output is correct
4 Correct 283 ms 5320 KB Output is correct
5 Correct 366 ms 4172 KB Output is correct
6 Correct 4 ms 336 KB Output is correct
7 Correct 4292 ms 58344 KB Output is correct
8 Correct 4453 ms 58440 KB Output is correct
9 Correct 271 ms 5180 KB Output is correct
10 Correct 3922 ms 58332 KB Output is correct
11 Correct 3703 ms 58344 KB Output is correct
12 Correct 3379 ms 58440 KB Output is correct
13 Correct 2653 ms 57588 KB Output is correct
14 Correct 2785 ms 55232 KB Output is correct
15 Correct 5509 ms 55236 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1828 ms 55236 KB Output is correct
18 Correct 1111 ms 7496 KB Output is correct
19 Correct 7356 ms 55236 KB Output is correct
20 Correct 6346 ms 55244 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 6229 ms 56348 KB Output is correct
24 Correct 1841 ms 57912 KB Output is correct
25 Correct 1051 ms 12148 KB Output is correct
26 Execution timed out 10057 ms 24880 KB Time limit exceeded
27 Halted 0 ms 0 KB -