oj.uz

Submission #1111987

# Submission time Handle Problem Language Result Execution time Memory
1111987 2024-11-13T13:25:24 Z onbert Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 79908 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); cout.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 1871 ms 5160 KB Output is correct
2 Correct 1850 ms 7208 KB Output is correct
3 Correct 1407 ms 7308 KB Output is correct
4 Correct 1304 ms 7316 KB Output is correct
5 Correct 1858 ms 6080 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 9114 ms 78468 KB Output is correct
2 Correct 8723 ms 79908 KB Output is correct
3 Correct 1327 ms 7240 KB Output is correct
4 Correct 5395 ms 79212 KB Output is correct
5 Correct 6523 ms 77564 KB Output is correct
6 Correct 6629 ms 78652 KB Output is correct
7 Correct 5753 ms 78448 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5859 ms 76716 KB Output is correct
2 Correct 5757 ms 76568 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2882 ms 78516 KB Output is correct
5 Correct 1720 ms 47124 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5859 ms 76716 KB Output is correct
2 Correct 5757 ms 76568 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2882 ms 78516 KB Output is correct
5 Correct 1720 ms 47124 KB Output is correct
6 Correct 6005 ms 76708 KB Output is correct
7 Correct 5726 ms 78668 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4600 KB Output is correct
10 Correct 5845 ms 75980 KB Output is correct
11 Correct 2972 ms 78240 KB Output is correct
12 Correct 1753 ms 49348 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1871 ms 5160 KB Output is correct
2 Correct 1850 ms 7208 KB Output is correct
3 Correct 1407 ms 7308 KB Output is correct
4 Correct 1304 ms 7316 KB Output is correct
5 Correct 1858 ms 6080 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 9281 ms 33844 KB Output is correct
8 Execution timed out 10038 ms 32756 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1871 ms 5160 KB Output is correct
2 Correct 1850 ms 7208 KB Output is correct
3 Correct 1407 ms 7308 KB Output is correct
4 Correct 1304 ms 7316 KB Output is correct
5 Correct 1858 ms 6080 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 9114 ms 78468 KB Output is correct
8 Correct 8723 ms 79908 KB Output is correct
9 Correct 1327 ms 7240 KB Output is correct
10 Correct 5395 ms 79212 KB Output is correct
11 Correct 6523 ms 77564 KB Output is correct
12 Correct 6629 ms 78652 KB Output is correct
13 Correct 5753 ms 78448 KB Output is correct
14 Correct 5859 ms 76716 KB Output is correct
15 Correct 5757 ms 76568 KB Output is correct
16 Correct 1 ms 4432 KB Output is correct
17 Correct 2882 ms 78516 KB Output is correct
18 Correct 1720 ms 47124 KB Output is correct
19 Correct 6005 ms 76708 KB Output is correct
20 Correct 5726 ms 78668 KB Output is correct
21 Correct 1 ms 4432 KB Output is correct
22 Correct 1 ms 4600 KB Output is correct
23 Correct 5845 ms 75980 KB Output is correct
24 Correct 2972 ms 78240 KB Output is correct
25 Correct 1753 ms 49348 KB Output is correct
26 Correct 9281 ms 33844 KB Output is correct
27 Execution timed out 10038 ms 32756 KB Time limit exceeded
28 Halted 0 ms 0 KB -