oj.uz

Submission #977945

# Submission time Handle Problem Language Result Execution time Memory
977945 2024-05-08T14:24:53 Z alextodoran Road Construction (JOI21_road_construction) C++17
100 / 100
 4743 ms 17200 KB 
/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

#define int long long

using namespace std;

typedef long long ll;

const int N_MAX = 250000;

int N, K;
struct Point {
    int x, y;
};
bool operator < (const Point &p1, const Point &p2) {
    return p1.x < p2.x;
}
Point P[N_MAX + 2];

int sorted_Y[N_MAX + 2];
int max_Y;

void compress () {
    for (int i = 1; i <= N; i++) {
        sorted_Y[i] = P[i].y;
    }
    sort(sorted_Y + 1, sorted_Y + N + 1);
    max_Y = (unique(sorted_Y + 1, sorted_Y + N + 1) - (sorted_Y + 1));
}

int Fen[N_MAX + 2];
void update (int pos, int val) {
    for (int i = pos; i <= max_Y; i += i & -i) {
        Fen[i] += val;
    }
}
int query (int pos) {
    int sum = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        sum += Fen[i];
    }
    return sum;
}
int query (int l, int r) {
    return query(r) - query(l - 1);
}

int find_l (int y) {
    int l = 1, r = max_Y + 1;
    while (l < r) {
        int mid = (l + r) / 2;
        if (y <= sorted_Y[mid]) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}
int find_r (int y) {
    int l = 0, r = max_Y;
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (sorted_Y[mid] <= y) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return r;
}

ll count_lower (int len) {
    ll answer = 0;
    for (int i = 1, j = 1; i <= N; i++) {
        while (P[i].x - P[j].x > len) {
            update(find_l(P[j++].y), -1);
        }
        answer += query(find_l(P[i].y - len), find_r(P[i].y + len));
        update(find_l(P[i].y), +1);
    }
    fill(Fen + 1, Fen + max_Y + 1, 0);
    return answer;
}

int answer[N_MAX + 2];

void solve (int len) {
    fill(answer + 1, answer + K + 1, len);
    len--;
    int curr = 0;
    set <pair <int, int>> S;
    for (int i = 1, j = 1; i <= N; i++) {
        while (P[i].x - P[j].x > len) {
            S.erase(make_pair(P[j].y, P[j].x)); j++;
        }
        set <pair <int, int>> :: iterator it = S.lower_bound(make_pair(P[i].y - len, LLONG_MIN));
        while (it != S.end() && it->first <= P[i].y + len) {
            answer[++curr] = max(P[i].x - it->second, abs(P[i].y - it->first));
            it++;
        }
        S.insert(make_pair(P[i].y, P[i].x));
    }
    sort(answer + 1, answer + curr + 1);
}

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> K;
    for (int i = 1; i <= N; i++) {
        int x, y;
        cin >> x >> y;
        P[i].x = x + y;
        P[i].y = x - y;
    }
    sort(P + 1, P + N + 1);
    compress();
    int l = 0, r = (ll) 4e9;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (count_lower(mid) >= K) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    solve(l);
    for (int i = 1; i <= K; i++) {
        cout << answer[i] << "\n";
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9044 KB Output is correct
2 Correct 39 ms 9040 KB Output is correct
3 Correct 34 ms 9052 KB Output is correct
4 Correct 33 ms 9040 KB Output is correct
5 Correct 36 ms 8020 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2028 ms 11592 KB Output is correct
2 Correct 2009 ms 11332 KB Output is correct
3 Correct 31 ms 9044 KB Output is correct
4 Correct 2019 ms 11080 KB Output is correct
5 Correct 1982 ms 11332 KB Output is correct
6 Correct 1990 ms 11332 KB Output is correct
7 Correct 1891 ms 10564 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4164 ms 8268 KB Output is correct
2 Correct 4116 ms 8272 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1974 ms 12964 KB Output is correct
5 Correct 2017 ms 13540 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4164 ms 8268 KB Output is correct
2 Correct 4116 ms 8272 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1974 ms 12964 KB Output is correct
5 Correct 2017 ms 13540 KB Output is correct
6 Correct 4126 ms 13364 KB Output is correct
7 Correct 4320 ms 13360 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 4078 ms 13360 KB Output is correct
11 Correct 2035 ms 12988 KB Output is correct
12 Correct 2057 ms 13372 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9044 KB Output is correct
2 Correct 39 ms 9040 KB Output is correct
3 Correct 34 ms 9052 KB Output is correct
4 Correct 33 ms 9040 KB Output is correct
5 Correct 36 ms 8020 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 1638 ms 12756 KB Output is correct
8 Correct 1650 ms 12752 KB Output is correct
9 Correct 35 ms 9080 KB Output is correct
10 Correct 1552 ms 11980 KB Output is correct
11 Correct 1476 ms 11976 KB Output is correct
12 Correct 700 ms 12472 KB Output is correct
13 Correct 753 ms 11092 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9044 KB Output is correct
2 Correct 39 ms 9040 KB Output is correct
3 Correct 34 ms 9052 KB Output is correct
4 Correct 33 ms 9040 KB Output is correct
5 Correct 36 ms 8020 KB Output is correct
6 Correct 4 ms 4444 KB Output is correct
7 Correct 2028 ms 11592 KB Output is correct
8 Correct 2009 ms 11332 KB Output is correct
9 Correct 31 ms 9044 KB Output is correct
10 Correct 2019 ms 11080 KB Output is correct
11 Correct 1982 ms 11332 KB Output is correct
12 Correct 1990 ms 11332 KB Output is correct
13 Correct 1891 ms 10564 KB Output is correct
14 Correct 4164 ms 8268 KB Output is correct
15 Correct 4116 ms 8272 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1974 ms 12964 KB Output is correct
18 Correct 2017 ms 13540 KB Output is correct
19 Correct 4126 ms 13364 KB Output is correct
20 Correct 4320 ms 13360 KB Output is correct
21 Correct 1 ms 4444 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 4078 ms 13360 KB Output is correct
24 Correct 2035 ms 12988 KB Output is correct
25 Correct 2057 ms 13372 KB Output is correct
26 Correct 1638 ms 12756 KB Output is correct
27 Correct 1650 ms 12752 KB Output is correct
28 Correct 35 ms 9080 KB Output is correct
29 Correct 1552 ms 11980 KB Output is correct
30 Correct 1476 ms 11976 KB Output is correct
31 Correct 700 ms 12472 KB Output is correct
32 Correct 753 ms 11092 KB Output is correct
33 Correct 4743 ms 17200 KB Output is correct
34 Correct 4738 ms 17156 KB Output is correct
35 Correct 4331 ms 16544 KB Output is correct
36 Correct 1883 ms 16984 KB Output is correct
37 Correct 1993 ms 16936 KB Output is correct
38 Correct 2151 ms 15664 KB Output is correct