oj.uz

Submission #977951

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

**/

#include <bits/stdc++.h>

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 (ll 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 (ll 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 (ll len) {
    ll answer = 0;
    for (int i = 1, j = 1; i <= N; i++) {
        while ((ll) 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;
}

ll answer[N_MAX + 2];

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

int 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();
    ll l = 0, r = (ll) 4e9;
    while (l < r) {
        ll mid = (l + r) / 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 47 ms 6992 KB Output is correct
2 Correct 44 ms 6996 KB Output is correct
3 Correct 42 ms 6980 KB Output is correct
4 Correct 36 ms 7076 KB Output is correct
5 Correct 40 ms 5972 KB Output is correct
6 Correct 4 ms 2396 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2110 ms 7420 KB Output is correct
2 Correct 2150 ms 7416 KB Output is correct
3 Correct 33 ms 6992 KB Output is correct
4 Correct 2090 ms 7160 KB Output is correct
5 Correct 2041 ms 7412 KB Output is correct
6 Correct 2164 ms 7416 KB Output is correct
7 Correct 2065 ms 6572 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4082 ms 4356 KB Output is correct
2 Correct 4200 ms 4356 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2084 ms 6132 KB Output is correct
5 Correct 2130 ms 4100 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4082 ms 4356 KB Output is correct
2 Correct 4200 ms 4356 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 2084 ms 6132 KB Output is correct
5 Correct 2130 ms 4100 KB Output is correct
6 Correct 4219 ms 4356 KB Output is correct
7 Correct 4329 ms 4360 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 4041 ms 4352 KB Output is correct
11 Correct 2069 ms 6136 KB Output is correct
12 Correct 2181 ms 4092 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6992 KB Output is correct
2 Correct 44 ms 6996 KB Output is correct
3 Correct 42 ms 6980 KB Output is correct
4 Correct 36 ms 7076 KB Output is correct
5 Correct 40 ms 5972 KB Output is correct
6 Correct 4 ms 2396 KB Output is correct
7 Correct 1608 ms 7024 KB Output is correct
8 Correct 1627 ms 7032 KB Output is correct
9 Correct 35 ms 7080 KB Output is correct
10 Correct 1544 ms 6256 KB Output is correct
11 Correct 1478 ms 6204 KB Output is correct
12 Correct 741 ms 6704 KB Output is correct
13 Correct 761 ms 5228 KB Output is correct

Subtask #6
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 6992 KB Output is correct
2 Correct 44 ms 6996 KB Output is correct
3 Correct 42 ms 6980 KB Output is correct
4 Correct 36 ms 7076 KB Output is correct
5 Correct 40 ms 5972 KB Output is correct
6 Correct 4 ms 2396 KB Output is correct
7 Correct 2110 ms 7420 KB Output is correct
8 Correct 2150 ms 7416 KB Output is correct
9 Correct 33 ms 6992 KB Output is correct
10 Correct 2090 ms 7160 KB Output is correct
11 Correct 2041 ms 7412 KB Output is correct
12 Correct 2164 ms 7416 KB Output is correct
13 Correct 2065 ms 6572 KB Output is correct
14 Correct 4082 ms 4356 KB Output is correct
15 Correct 4200 ms 4356 KB Output is correct
16 Correct 1 ms 2392 KB Output is correct
17 Correct 2084 ms 6132 KB Output is correct
18 Correct 2130 ms 4100 KB Output is correct
19 Correct 4219 ms 4356 KB Output is correct
20 Correct 4329 ms 4360 KB Output is correct
21 Correct 1 ms 2392 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 4041 ms 4352 KB Output is correct
24 Correct 2069 ms 6136 KB Output is correct
25 Correct 2181 ms 4092 KB Output is correct
26 Correct 1608 ms 7024 KB Output is correct
27 Correct 1627 ms 7032 KB Output is correct
28 Correct 35 ms 7080 KB Output is correct
29 Correct 1544 ms 6256 KB Output is correct
30 Correct 1478 ms 6204 KB Output is correct
31 Correct 741 ms 6704 KB Output is correct
32 Correct 761 ms 5228 KB Output is correct
33 Correct 4613 ms 8208 KB Output is correct
34 Correct 4518 ms 8128 KB Output is correct
35 Correct 4066 ms 7592 KB Output is correct
36 Correct 1960 ms 7680 KB Output is correct
37 Correct 2041 ms 7940 KB Output is correct
38 Correct 2184 ms 6432 KB Output is correct