oj.uz

Submission #977949

# Submission time Handle Problem Language Result Execution time Memory
977949 2024-05-08T14:27:12 Z alextodoran Road Construction (JOI21_road_construction) C++17
59 / 100
 4081 ms 12532 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 (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 (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 57 ms 7156 KB Output is correct
2 Correct 58 ms 7248 KB Output is correct
3 Correct 38 ms 6996 KB Output is correct
4 Correct 36 ms 6996 KB Output is correct
5 Correct 50 ms 6156 KB Output is correct
6 Correct 4 ms 2392 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2067 ms 7420 KB Output is correct
2 Correct 2060 ms 7508 KB Output is correct
3 Correct 33 ms 6812 KB Output is correct
4 Correct 2055 ms 7252 KB Output is correct
5 Runtime error 1315 ms 12532 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4062 ms 4436 KB Output is correct
2 Correct 4066 ms 4364 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2013 ms 6140 KB Output is correct
5 Correct 2045 ms 4180 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4062 ms 4436 KB Output is correct
2 Correct 4066 ms 4364 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 2013 ms 6140 KB Output is correct
5 Correct 2045 ms 4180 KB Output is correct
6 Correct 4010 ms 4356 KB Output is correct
7 Correct 4081 ms 4356 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 0 ms 2396 KB Output is correct
10 Correct 3831 ms 4356 KB Output is correct
11 Correct 2021 ms 6140 KB Output is correct
12 Correct 2043 ms 4200 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 7156 KB Output is correct
2 Correct 58 ms 7248 KB Output is correct
3 Correct 38 ms 6996 KB Output is correct
4 Correct 36 ms 6996 KB Output is correct
5 Correct 50 ms 6156 KB Output is correct
6 Correct 4 ms 2392 KB Output is correct
7 Correct 1543 ms 7024 KB Output is correct
8 Correct 1569 ms 7252 KB Output is correct
9 Correct 37 ms 7204 KB Output is correct
10 Correct 1481 ms 6368 KB Output is correct
11 Correct 1425 ms 6256 KB Output is correct
12 Correct 714 ms 6736 KB Output is correct
13 Correct 752 ms 5232 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 7156 KB Output is correct
2 Correct 58 ms 7248 KB Output is correct
3 Correct 38 ms 6996 KB Output is correct
4 Correct 36 ms 6996 KB Output is correct
5 Correct 50 ms 6156 KB Output is correct
6 Correct 4 ms 2392 KB Output is correct
7 Correct 2067 ms 7420 KB Output is correct
8 Correct 2060 ms 7508 KB Output is correct
9 Correct 33 ms 6812 KB Output is correct
10 Correct 2055 ms 7252 KB Output is correct
11 Runtime error 1315 ms 12532 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -