oj.uz

Submission #443783

# Submission time Handle Problem Language Result Execution time Memory
443783 2021-07-12T05:38:11 Z PeppaPig Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 569100 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 33712 KB Output is correct
2 Correct 130 ms 33672 KB Output is correct
3 Incorrect 109 ms 33712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10041 ms 569100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10070 ms 47024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10070 ms 47024 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 33712 KB Output is correct
2 Correct 130 ms 33672 KB Output is correct
3 Incorrect 109 ms 33712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 33712 KB Output is correct
2 Correct 130 ms 33672 KB Output is correct
3 Incorrect 109 ms 33712 KB Output isn't correct
4 Halted 0 ms 0 KB -