oj.uz

Submission #977944

# Submission time Handle Problem Language Result Execution time Memory
977944 2024-05-08T14:20:54 Z alextodoran Road Construction (JOI21_road_construction) C++17
6 / 100
 4150 ms 14416 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, INT_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 = (int) 2e9;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9048 KB Output is correct
2 Correct 40 ms 9040 KB Output is correct
3 Incorrect 33 ms 9040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2036 ms 11320 KB Output is correct
2 Correct 2013 ms 11332 KB Output is correct
3 Correct 34 ms 9044 KB Output is correct
4 Correct 2068 ms 14136 KB Output is correct
5 Correct 1973 ms 14416 KB Output is correct
6 Correct 1955 ms 14364 KB Output is correct
7 Correct 1876 ms 13728 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4021 ms 8272 KB Output is correct
2 Correct 4150 ms 8272 KB Output is correct
3 Incorrect 1 ms 4440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4021 ms 8272 KB Output is correct
2 Correct 4150 ms 8272 KB Output is correct
3 Incorrect 1 ms 4440 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9048 KB Output is correct
2 Correct 40 ms 9040 KB Output is correct
3 Incorrect 33 ms 9040 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 9048 KB Output is correct
2 Correct 40 ms 9040 KB Output is correct
3 Incorrect 33 ms 9040 KB Output isn't correct
4 Halted 0 ms 0 KB -