oj.uz

Submission #1111985

# Submission time Handle Problem Language Result Execution time Memory
1111985 2024-11-13T13:20:33 Z onbert Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 83096 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 250005, inf = 2e9 + 10;
const ll INF = 4e9 + 10;
int n, k;
pair<int, int> a[maxn];
int sz;
vector<int> vals = {-inf};
int norm(ll x) {return min(max(x, -(ll)inf), (ll)inf);}
int ldc(ll x) {return lower_bound(vals.begin(), vals.end(), x) - vals.begin();}
int rdc(ll x) {return upper_bound(vals.begin(), vals.end(), x) - vals.begin() - 1;}

struct node {
    int lpt, rpt, val;
};

struct thing {
    ll id, dist, cnt;
    bool operator < (const thing &b) const {
        return dist > b.dist;
    }
};

pair<ll, ll> b[maxn];
node seg[17931578];
int pt = 1;
vector<int> lg = {1};
void build(int id, int l, int r) {
    seg[id] = {0, 0, 0};
    if (l==r) return;
    int mid = (l+r) >> 1;
    seg[id].lpt = pt++;
    build(pt, l, mid);
    seg[id].rpt = pt++;
    build(pt, mid+1, r);
}
void update(int id, int l, int r, int target) {
    seg[id].val++;
    if (l==r) return;
    int mid = (l+r) >> 1;
    pt++;
    if (target<=mid) {
        seg[pt] = seg[seg[id].lpt];
        seg[id].lpt = pt;
        update(pt, l, mid, target);
    } else {
        seg[pt] = seg[seg[id].rpt];
        seg[id].rpt = pt;
        update(pt, mid+1, r, target);
    }
}
int qry(int id, int l, int r, int findl, int findr) {
    if (r<findl || findr<l) return 0;
    if (findl<=l && r<=findr) return seg[id].val;
    int mid = (l+r) >> 1;
    int lhs = qry(seg[id].lpt, l, mid, findl, findr);
    int rhs = qry(seg[id].rpt, mid+1, r, findl, findr);
    return lhs + rhs;
}


int cunt(ll id, ll dist) {
    int L = ldc(norm(a[id].second - dist)), R = rdc(norm(a[id].second + dist));
    int val = qry(lg[id], 1, sz, L, R);
    int x = lower_bound(a+1, a+n+1, make_pair(norm(a[id].first - dist), -inf)) - a - 1;
    val -= qry(lg[x], 1, sz, L, R);
    return val;
}

priority_queue<thing> pq;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for (int i=1;i<=n;i++) {
        int x, y;
        cin >> x >> y;
        a[i] = {x+y, x-y};
        vals.push_back(x-y);
    }
    sort(a+1, a+n+1);
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    sz = vals.size() - 1;
    build(1, 1, sz);
    for (int i=1;i<=n;i++) {
        pt++;
        seg[pt] = seg[lg.back()];
        lg.push_back(pt);
        update(pt, 1, sz, ldc(a[i].second));
    }
    for (int i=2;i<=n;i++) {
        b[i] = {0, 1};
        ll l = 1, r = INF;
        while (l < r) {
            ll mid = (l+r)/2;
            if (cunt(i, mid) == b[i].second) l = mid+1;
            else r = mid;
        }
        int x = cunt(i, l);
        pq.push({i, l, x});
        // cout << i << " " << l << " " << cunt(i, l) << endl;
    }
    int total = 0;
    while (true) {
        ll id = pq.top().id, dist = pq.top().dist, cnt = pq.top().cnt;
        pq.pop();
        // cout << id << " " << dist << " " << cnt << endl;
        for (;b[id].second<cnt;b[id].second++) {
            cout << dist << '\n';
            total++;
            if (total == k) return 0;
        }
        if (b[id].second == id) continue;
        b[id].first = dist;
        ll l = dist+1, r = INF;
        while (l < r) {
            ll mid = (l+r) >> 1;
            if (cunt(id, mid) == b[id].second) l = mid+1;
            else r = mid;
        }
        int x = cunt(id, l);
        pq.push({id, l, x});
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1934 ms 7200 KB Output is correct
2 Correct 1956 ms 7332 KB Output is correct
3 Correct 1413 ms 7264 KB Output is correct
4 Correct 1198 ms 7244 KB Output is correct
5 Correct 1695 ms 6164 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8405 ms 79356 KB Output is correct
2 Correct 8662 ms 80300 KB Output is correct
3 Correct 1327 ms 7240 KB Output is correct
4 Correct 5091 ms 80236 KB Output is correct
5 Correct 6270 ms 78892 KB Output is correct
6 Correct 6271 ms 79636 KB Output is correct
7 Correct 5766 ms 79500 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5515 ms 81852 KB Output is correct
2 Correct 5870 ms 76748 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2896 ms 79288 KB Output is correct
5 Correct 1690 ms 51352 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5515 ms 81852 KB Output is correct
2 Correct 5870 ms 76748 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2896 ms 79288 KB Output is correct
5 Correct 1690 ms 51352 KB Output is correct
6 Correct 5793 ms 80588 KB Output is correct
7 Correct 5678 ms 79860 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 5951 ms 75968 KB Output is correct
11 Correct 2879 ms 78984 KB Output is correct
12 Correct 1734 ms 51404 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1934 ms 7200 KB Output is correct
2 Correct 1956 ms 7332 KB Output is correct
3 Correct 1413 ms 7264 KB Output is correct
4 Correct 1198 ms 7244 KB Output is correct
5 Correct 1695 ms 6164 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 8066 ms 34568 KB Output is correct
8 Correct 8400 ms 32652 KB Output is correct
9 Correct 1219 ms 7328 KB Output is correct
10 Correct 3808 ms 31368 KB Output is correct
11 Correct 5008 ms 34264 KB Output is correct
12 Correct 878 ms 26300 KB Output is correct
13 Correct 1749 ms 23508 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1934 ms 7200 KB Output is correct
2 Correct 1956 ms 7332 KB Output is correct
3 Correct 1413 ms 7264 KB Output is correct
4 Correct 1198 ms 7244 KB Output is correct
5 Correct 1695 ms 6164 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 8405 ms 79356 KB Output is correct
8 Correct 8662 ms 80300 KB Output is correct
9 Correct 1327 ms 7240 KB Output is correct
10 Correct 5091 ms 80236 KB Output is correct
11 Correct 6270 ms 78892 KB Output is correct
12 Correct 6271 ms 79636 KB Output is correct
13 Correct 5766 ms 79500 KB Output is correct
14 Correct 5515 ms 81852 KB Output is correct
15 Correct 5870 ms 76748 KB Output is correct
16 Correct 1 ms 4432 KB Output is correct
17 Correct 2896 ms 79288 KB Output is correct
18 Correct 1690 ms 51352 KB Output is correct
19 Correct 5793 ms 80588 KB Output is correct
20 Correct 5678 ms 79860 KB Output is correct
21 Correct 1 ms 4432 KB Output is correct
22 Correct 2 ms 4432 KB Output is correct
23 Correct 5951 ms 75968 KB Output is correct
24 Correct 2879 ms 78984 KB Output is correct
25 Correct 1734 ms 51404 KB Output is correct
26 Correct 8066 ms 34568 KB Output is correct
27 Correct 8400 ms 32652 KB Output is correct
28 Correct 1219 ms 7328 KB Output is correct
29 Correct 3808 ms 31368 KB Output is correct
30 Correct 5008 ms 34264 KB Output is correct
31 Correct 878 ms 26300 KB Output is correct
32 Correct 1749 ms 23508 KB Output is correct
33 Execution timed out 10030 ms 83096 KB Time limit exceeded
34 Halted 0 ms 0 KB -