oj.uz

Submission #444048

# Submission time Handle Problem Language Result Execution time Memory
444048 2021-07-13T04:03:13 Z PeppaPig Road Construction (JOI21_road_construction) C++14
0 / 100
 10000 ms 566284 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) {
            update(get(A[j].y), -1, j);
            ++j;
        }
 
        vector<int> idx;
        get_answer(get(A[i].y - r), get(A[i].y + r + 1) - 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(int i = 0; i < k; i++) printf("%lld\n", ans[i]);
 
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
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 115 ms 33712 KB Output is correct
2 Correct 116 ms 33720 KB Output is correct
3 Incorrect 93 ms 33148 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 10102 ms 566284 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 10065 ms 42040 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 10065 ms 42040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 33712 KB Output is correct
2 Correct 116 ms 33720 KB Output is correct
3 Incorrect 93 ms 33148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 33712 KB Output is correct
2 Correct 116 ms 33720 KB Output is correct
3 Incorrect 93 ms 33148 KB Output isn't correct
4 Halted 0 ms 0 KB -