oj.uz

Submission #1112103

# Submission time Handle Problem Language Result Execution time Memory
1112103 2024-11-13T16:32:22 Z onbert Road Construction (JOI21_road_construction) C++17
100 / 100
 5598 ms 23628 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, INF = 6e9 + 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 58 ms 9416 KB Output is correct
2 Correct 59 ms 9316 KB Output is correct
3 Correct 77 ms 9392 KB Output is correct
4 Correct 58 ms 9392 KB Output is correct
5 Correct 54 ms 5900 KB Output is correct
6 Correct 3 ms 2564 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1897 ms 16664 KB Output is correct
2 Correct 1771 ms 16664 KB Output is correct
3 Correct 50 ms 9140 KB Output is correct
4 Correct 1808 ms 16656 KB Output is correct
5 Correct 1998 ms 16680 KB Output is correct
6 Correct 2001 ms 16660 KB Output is correct
7 Correct 1696 ms 16672 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4549 ms 10412 KB Output is correct
2 Correct 4607 ms 10412 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1991 ms 13484 KB Output is correct
5 Correct 1470 ms 14508 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4549 ms 10412 KB Output is correct
2 Correct 4607 ms 10412 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1991 ms 13484 KB Output is correct
5 Correct 1470 ms 14508 KB Output is correct
6 Correct 4629 ms 14232 KB Output is correct
7 Correct 4811 ms 14352 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 4705 ms 15448 KB Output is correct
11 Correct 1950 ms 13148 KB Output is correct
12 Correct 1387 ms 15276 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9416 KB Output is correct
2 Correct 59 ms 9316 KB Output is correct
3 Correct 77 ms 9392 KB Output is correct
4 Correct 58 ms 9392 KB Output is correct
5 Correct 54 ms 5900 KB Output is correct
6 Correct 3 ms 2564 KB Output is correct
7 Correct 1906 ms 14604 KB Output is correct
8 Correct 1954 ms 14432 KB Output is correct
9 Correct 53 ms 9392 KB Output is correct
10 Correct 1692 ms 14648 KB Output is correct
11 Correct 1610 ms 14596 KB Output is correct
12 Correct 266 ms 14372 KB Output is correct
13 Correct 343 ms 14480 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9416 KB Output is correct
2 Correct 59 ms 9316 KB Output is correct
3 Correct 77 ms 9392 KB Output is correct
4 Correct 58 ms 9392 KB Output is correct
5 Correct 54 ms 5900 KB Output is correct
6 Correct 3 ms 2564 KB Output is correct
7 Correct 1897 ms 16664 KB Output is correct
8 Correct 1771 ms 16664 KB Output is correct
9 Correct 50 ms 9140 KB Output is correct
10 Correct 1808 ms 16656 KB Output is correct
11 Correct 1998 ms 16680 KB Output is correct
12 Correct 2001 ms 16660 KB Output is correct
13 Correct 1696 ms 16672 KB Output is correct
14 Correct 4549 ms 10412 KB Output is correct
15 Correct 4607 ms 10412 KB Output is correct
16 Correct 1 ms 2384 KB Output is correct
17 Correct 1991 ms 13484 KB Output is correct
18 Correct 1470 ms 14508 KB Output is correct
19 Correct 4629 ms 14232 KB Output is correct
20 Correct 4811 ms 14352 KB Output is correct
21 Correct 1 ms 2384 KB Output is correct
22 Correct 1 ms 2384 KB Output is correct
23 Correct 4705 ms 15448 KB Output is correct
24 Correct 1950 ms 13148 KB Output is correct
25 Correct 1387 ms 15276 KB Output is correct
26 Correct 1906 ms 14604 KB Output is correct
27 Correct 1954 ms 14432 KB Output is correct
28 Correct 53 ms 9392 KB Output is correct
29 Correct 1692 ms 14648 KB Output is correct
30 Correct 1610 ms 14596 KB Output is correct
31 Correct 266 ms 14372 KB Output is correct
32 Correct 343 ms 14480 KB Output is correct
33 Correct 5503 ms 21788 KB Output is correct
34 Correct 5598 ms 21784 KB Output is correct
35 Correct 4481 ms 21752 KB Output is correct
36 Correct 646 ms 21900 KB Output is correct
37 Correct 672 ms 21580 KB Output is correct
38 Correct 1315 ms 23628 KB Output is correct