oj.uz

Submission #1112098

# Submission time Handle Problem Language Result Execution time Memory
1112098 2024-11-13T16:26:26 Z onbert Road Construction (JOI21_road_construction) C++17
100 / 100
 5642 ms 23640 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 58 ms 9160 KB Output is correct
2 Correct 62 ms 9348 KB Output is correct
3 Correct 52 ms 9408 KB Output is correct
4 Correct 55 ms 9400 KB Output is correct
5 Correct 52 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 1788 ms 16660 KB Output is correct
2 Correct 1840 ms 16684 KB Output is correct
3 Correct 49 ms 9136 KB Output is correct
4 Correct 1811 ms 16664 KB Output is correct
5 Correct 1992 ms 16684 KB Output is correct
6 Correct 1894 ms 16660 KB Output is correct
7 Correct 1720 ms 16684 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4707 ms 10412 KB Output is correct
2 Correct 4750 ms 10416 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1949 ms 10480 KB Output is correct
5 Correct 1444 ms 10412 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4707 ms 10412 KB Output is correct
2 Correct 4750 ms 10416 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 1949 ms 10480 KB Output is correct
5 Correct 1444 ms 10412 KB Output is correct
6 Correct 4656 ms 10632 KB Output is correct
7 Correct 4654 ms 10412 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 4531 ms 10420 KB Output is correct
11 Correct 1942 ms 10412 KB Output is correct
12 Correct 1416 ms 10412 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9160 KB Output is correct
2 Correct 62 ms 9348 KB Output is correct
3 Correct 52 ms 9408 KB Output is correct
4 Correct 55 ms 9400 KB Output is correct
5 Correct 52 ms 8640 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 2001 ms 12560 KB Output is correct
8 Correct 1943 ms 14416 KB Output is correct
9 Correct 59 ms 9388 KB Output is correct
10 Correct 1708 ms 14656 KB Output is correct
11 Correct 1641 ms 14596 KB Output is correct
12 Correct 260 ms 14400 KB Output is correct
13 Correct 409 ms 14564 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9160 KB Output is correct
2 Correct 62 ms 9348 KB Output is correct
3 Correct 52 ms 9408 KB Output is correct
4 Correct 55 ms 9400 KB Output is correct
5 Correct 52 ms 8640 KB Output is correct
6 Correct 3 ms 2384 KB Output is correct
7 Correct 1788 ms 16660 KB Output is correct
8 Correct 1840 ms 16684 KB Output is correct
9 Correct 49 ms 9136 KB Output is correct
10 Correct 1811 ms 16664 KB Output is correct
11 Correct 1992 ms 16684 KB Output is correct
12 Correct 1894 ms 16660 KB Output is correct
13 Correct 1720 ms 16684 KB Output is correct
14 Correct 4707 ms 10412 KB Output is correct
15 Correct 4750 ms 10416 KB Output is correct
16 Correct 1 ms 2384 KB Output is correct
17 Correct 1949 ms 10480 KB Output is correct
18 Correct 1444 ms 10412 KB Output is correct
19 Correct 4656 ms 10632 KB Output is correct
20 Correct 4654 ms 10412 KB Output is correct
21 Correct 1 ms 2384 KB Output is correct
22 Correct 1 ms 2384 KB Output is correct
23 Correct 4531 ms 10420 KB Output is correct
24 Correct 1942 ms 10412 KB Output is correct
25 Correct 1416 ms 10412 KB Output is correct
26 Correct 2001 ms 12560 KB Output is correct
27 Correct 1943 ms 14416 KB Output is correct
28 Correct 59 ms 9388 KB Output is correct
29 Correct 1708 ms 14656 KB Output is correct
30 Correct 1641 ms 14596 KB Output is correct
31 Correct 260 ms 14400 KB Output is correct
32 Correct 409 ms 14564 KB Output is correct
33 Correct 5540 ms 21796 KB Output is correct
34 Correct 5642 ms 21788 KB Output is correct
35 Correct 4780 ms 21752 KB Output is correct
36 Correct 657 ms 21900 KB Output is correct
37 Correct 653 ms 21544 KB Output is correct
38 Correct 1220 ms 23640 KB Output is correct