oj.uz

Submission #1112099

# Submission time Handle Problem Language Result Execution time Memory
1112099 2024-11-13T16:26:39 Z onbert Road Construction (JOI21_road_construction) C++17
100 / 100
 5526 ms 18348 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, INF = 1e10 + 10;
int n, k;
pair<int, int> a[maxn];
int ysz;
vector<int> xvals = {-INF}, yvals = {-INF};
int ldc(int x) {return lower_bound(yvals.begin(), yvals.end(), x) - yvals.begin();}
int rdc(int x) {return upper_bound(yvals.begin(), yvals.end(), x) - yvals.begin() - 1;}

int fen[maxn];
void update(int id) {
    while (id <= ysz) {
        fen[id]++;
        id += (id & -id);
    } 
}
int qry(int id) {
    int val = 0;
    while (id >= 1) {
        val += fen[id];
        id -= (id & -id);
    }
    return val;
}

int cunt(int dist) {
    int ans = 0, pt = 0;
    for (int i=1;i<=n;i++) {
        while (pt+1 <= n && a[pt+1].first <= a[i].first + dist) {
            pt++;
            int L = ldc(a[pt].second - dist), R = rdc(a[pt].second + dist);
            ans -= qry(R) - qry(L-1);
            // cout << "- " << (a[pt].first+a[pt].second)/2 << " " << (a[pt].first-a[pt].second)/2 << " " << qry(R) - qry(L-1) << endl;
        }
        int L = ldc(a[i].second - dist), R = rdc(a[i].second + dist);
        ans += qry(R) - qry(L-1);
        // cout << "+ " << (a[i].first+a[i].second)/2 << " " << (a[i].first-a[i].second)/2 << " " << qry(R) - qry(L-1) << endl;
        int pos = ldc(a[i].second);
        update(pos);
    }
    return ans;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x+y, x-y};
        xvals.push_back(x+y);
        yvals.push_back(x-y);
    }
    sort(a+1, a+n+1);
    sort(xvals.begin(), xvals.end());
    xvals.erase(unique(xvals.begin(), xvals.end()), xvals.end());
    sort(yvals.begin(), yvals.end());
    yvals.erase(unique(yvals.begin(), yvals.end()), yvals.end());
    ysz = yvals.size() - 1;

    int L = 1, R = INF;
    while (L < R) {
        int mid = (L+R)/2;
        if (cunt(mid) < k) L = mid+1;
        else R = mid;
    }
    
    int dist = L - 1;
    vector<int> ans;
    multiset<pair<int,int>> s;
    s.insert({INF, INF});
    int l = 0, r = 0;
    int cnt = 0;
    for (int i=1;i<=n;i++) {
        while (r+1 <= n && a[r+1].first <= a[i].first + dist) {
            r++;
            s.insert({a[r].second, a[r].first});
        }
        while (l+1 <= n && a[l+1].first < a[i].first - dist) {
            l++;
            s.erase({a[l].second, a[l].first});
        }

        // cout << "test\n";
        // cout << (a[i].first+a[i].second)/2 << " " << (a[i].first-a[i].second)/2 << endl;

        auto it = s.lower_bound({a[i].second - dist, -INF});
        while ((it->first) <= a[i].second + dist) {
            pair<int,int> cur = *it;
            if (a[i].first!=cur.second || a[i].second!=cur.first) {
                ans.push_back(max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)));
                // assert(max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)) <= dist);
                cnt++;
                // cout << max(abs(a[i].first - cur.second), abs(a[i].second - cur.first)) << endl;
            }
            it++;
        }
    }
    while (ans.size() < 2*k) ans.push_back(L);
    sort(ans.begin(), ans.end());
    for (int i=0;i<2*k;i+=2) cout << ans[i] << '\n';
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:101: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]
  101 |     while (ans.size() < 2*k) ans.push_back(L);
      |            ~~~~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9160 KB Output is correct
2 Correct 58 ms 9344 KB Output is correct
3 Correct 56 ms 9368 KB Output is correct
4 Correct 54 ms 9392 KB Output is correct
5 Correct 79 ms 8640 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1823 ms 16688 KB Output is correct
2 Correct 1845 ms 16660 KB Output is correct
3 Correct 55 ms 9116 KB Output is correct
4 Correct 1848 ms 16664 KB Output is correct
5 Correct 1945 ms 16656 KB Output is correct
6 Correct 2001 ms 16656 KB Output is correct
7 Correct 1647 ms 16656 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4591 ms 10412 KB Output is correct
2 Correct 4556 ms 10420 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1928 ms 10508 KB Output is correct
5 Correct 1420 ms 10412 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4591 ms 10412 KB Output is correct
2 Correct 4556 ms 10420 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1928 ms 10508 KB Output is correct
5 Correct 1420 ms 10412 KB Output is correct
6 Correct 4677 ms 10412 KB Output is correct
7 Correct 4764 ms 10476 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 4650 ms 10444 KB Output is correct
11 Correct 1944 ms 10412 KB Output is correct
12 Correct 1425 ms 10412 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9160 KB Output is correct
2 Correct 58 ms 9344 KB Output is correct
3 Correct 56 ms 9368 KB Output is correct
4 Correct 54 ms 9392 KB Output is correct
5 Correct 79 ms 8640 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 1979 ms 12560 KB Output is correct
8 Correct 2019 ms 12392 KB Output is correct
9 Correct 52 ms 9372 KB Output is correct
10 Correct 1730 ms 12548 KB Output is correct
11 Correct 1599 ms 12560 KB Output is correct
12 Correct 274 ms 12352 KB Output is correct
13 Correct 394 ms 12432 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 9160 KB Output is correct
2 Correct 58 ms 9344 KB Output is correct
3 Correct 56 ms 9368 KB Output is correct
4 Correct 54 ms 9392 KB Output is correct
5 Correct 79 ms 8640 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 1823 ms 16688 KB Output is correct
8 Correct 1845 ms 16660 KB Output is correct
9 Correct 55 ms 9116 KB Output is correct
10 Correct 1848 ms 16664 KB Output is correct
11 Correct 1945 ms 16656 KB Output is correct
12 Correct 2001 ms 16656 KB Output is correct
13 Correct 1647 ms 16656 KB Output is correct
14 Correct 4591 ms 10412 KB Output is correct
15 Correct 4556 ms 10420 KB Output is correct
16 Correct 1 ms 2384 KB Output is correct
17 Correct 1928 ms 10508 KB Output is correct
18 Correct 1420 ms 10412 KB Output is correct
19 Correct 4677 ms 10412 KB Output is correct
20 Correct 4764 ms 10476 KB Output is correct
21 Correct 1 ms 2384 KB Output is correct
22 Correct 1 ms 2384 KB Output is correct
23 Correct 4650 ms 10444 KB Output is correct
24 Correct 1944 ms 10412 KB Output is correct
25 Correct 1425 ms 10412 KB Output is correct
26 Correct 1979 ms 12560 KB Output is correct
27 Correct 2019 ms 12392 KB Output is correct
28 Correct 52 ms 9372 KB Output is correct
29 Correct 1730 ms 12548 KB Output is correct
30 Correct 1599 ms 12560 KB Output is correct
31 Correct 274 ms 12352 KB Output is correct
32 Correct 394 ms 12432 KB Output is correct
33 Correct 5386 ms 16712 KB Output is correct
34 Correct 5526 ms 16708 KB Output is correct
35 Correct 4780 ms 16676 KB Output is correct
36 Correct 681 ms 16460 KB Output is correct
37 Correct 707 ms 16472 KB Output is correct
38 Correct 1235 ms 18348 KB Output is correct