Submission #443783

#	Time	Username	Problem	Language	Result	Execution time	Memory
443783		PeppaPig	Road Construction (JOI21_road_construction)	C++14	0 / 100	10070 ms	569100 KiB

road_construction

#include <bits/stdc++.h>

#define long long long
#define pii pair<long, long>
#define x first
#define y second

using namespace std;

const int N = 1 << 19;

set<int> leaf[N];
int t[N << 1];

void update(int x, int k, int idx, int p = 1, int l = 1, int r = N) {
    if(l > x || x > r) return;
    if(l == r) {
        t[p] += k;
        if(k == 1) leaf[l].emplace(idx);
        else leaf[l].erase(idx);
        return;
    }
    int mid = (l + r) >> 1;
    update(x, k, idx, p << 1, l, mid), update(x, k, idx, p << 1 | 1, mid + 1, r);
    t[p] = t[p << 1] + t[p << 1 | 1];
}

int query(int x, int y, int p = 1, int l = 1, int r = N) {
    if(x > r || l > y) return 0;
    if(x <= l && r <= y) return t[p];
    int mid = (l + r) >> 1;
    return query(x, y, p << 1, l, mid) + query(x, y, p << 1 | 1, mid + 1, r);
}

void get_answer(int x, int y, vector<int> &vec, int p = 1, int l = 1, int r = N) {
    if(x > r || l > y || !t[p]) return;
    if(l == r) {
        for(int x : leaf[l]) vec.emplace_back(x);
        return;
    }
    int mid = (l + r) >> 1;
    get_answer(x, y, vec, p << 1, l, mid), get_answer(x, y, vec, p << 1 | 1, mid + 1, r);
}

int n, k;
pii A[N];
vector<long> coord;

int get(long x) {
    return lower_bound(coord.begin(), coord.end(), x) - coord.begin() + 1;
}

int main() {
    scanf("%d %d", &n, &k);

    for(int i = 1; i <= n; i++) {
        long a, b;
        scanf("%lld %lld", &a, &b);
        A[i] = pii(a + b, a - b);
        coord.emplace_back(A[i].y);
    }
    sort(A + 1, A + n + 1);
    sort(coord.begin(), coord.end());
    coord.resize(unique(coord.begin(), coord.end()) - coord.begin());

    long l = 0, r = 2e9;
    while(l < r) {
        long mid = (l + r) >> 1;

        memset(t, 0, sizeof t);
        for(int i = 1; i <= n; i++) leaf[i].clear();

        int cnt = 0;
        for(int i = 1, j = 1; i <= n; i++) {
            while(j < i && A[i].x - A[j].x > mid) {
                update(get(A[j].y), -1, j);
                ++j;
            }

            cnt += query(get(A[i].y - mid), get(A[i].y + mid + 1) - 1);
            update(get(A[i].y), 1, i);
        }

        if(cnt >= k) r = mid;
        else l = mid + 1;
    }

    vector<long> ans;

    memset(t, 0, sizeof t);
    for(int i = 1; i <= n; i++) leaf[i].clear();

    for(int i = 1, j = 1; i <= n; i++) {
        while(j < i && A[i].x - A[j].x > r - 1) {
            update(get(A[j].y), -1, j);
            ++j;
        }

        vector<int> idx;
        get_answer(get(A[i].y - r + 1), get(A[i].y + r) - 1, idx);
        for(int x : idx) {
            long ta = A[i].x - A[x].x;
            long tb = A[i].y - A[x].y;

            ans.emplace_back(abs((ta + tb) / 2) + abs((ta - tb) / 2));
        }

        update(get(A[i].y), 1, i);
    }
    while(ans.size() < k) ans.emplace_back(r);
    sort(ans.begin(), ans.end());
    for(long x : ans) printf("%lld\n", x);

    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:110:22: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  110 |     while(ans.size() < k) ans.emplace_back(r);
      |           ~~~~~~~~~~~^~~
road_construction.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
road_construction.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf("%lld %lld", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 0 / 27
• Subtask 6: 0 / 35