Submission #977951

#	Time	Username	Problem	Language	Result	Execution time	Memory
977951		alextodoran	Road Construction (JOI21_road_construction)	C++17	100 / 100	4613 ms	8208 KiB

road_construction

/**
 _  _   __  _ _ _  _  _ _
 |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 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 35 / 35