oj.uz

Submission #1112005

# Submission time Handle Problem Language Result Execution time Memory
1112005 2024-11-13T13:50:53 Z tosivanmak Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 77036 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2","sse4")
#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];
ll onbert[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;
    bool operator < (const thing &b) const {
        return dist > b.dist;
    }
};
 
pair<ll, ll> b[maxn];
node seg[10000000];
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});
        onbert[i] = x;
        // cout << i << " " << l << " " << cunt(i, l) << endl;
    }
    int total = 0;
    while (true) {
        ll id = pq.top().id, dist = pq.top().dist; ll cnt = onbert[id];
        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}); onbert[id] = x;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1513 ms 7240 KB Output is correct
2 Correct 1482 ms 7224 KB Output is correct
3 Correct 1169 ms 7244 KB Output is correct
4 Correct 1042 ms 7376 KB Output is correct
5 Correct 1523 ms 4168 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7129 ms 76860 KB Output is correct
2 Correct 7422 ms 77016 KB Output is correct
3 Correct 1116 ms 7008 KB Output is correct
4 Correct 4457 ms 76660 KB Output is correct
5 Correct 5271 ms 77036 KB Output is correct
6 Correct 5400 ms 76844 KB Output is correct
7 Correct 4848 ms 76228 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4851 ms 75712 KB Output is correct
2 Correct 5029 ms 75992 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2576 ms 75912 KB Output is correct
5 Correct 1495 ms 46464 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4851 ms 75712 KB Output is correct
2 Correct 5029 ms 75992 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2576 ms 75912 KB Output is correct
5 Correct 1495 ms 46464 KB Output is correct
6 Correct 4767 ms 75596 KB Output is correct
7 Correct 4996 ms 75632 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 4749 ms 74924 KB Output is correct
11 Correct 2519 ms 75680 KB Output is correct
12 Correct 1441 ms 46460 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1513 ms 7240 KB Output is correct
2 Correct 1482 ms 7224 KB Output is correct
3 Correct 1169 ms 7244 KB Output is correct
4 Correct 1042 ms 7376 KB Output is correct
5 Correct 1523 ms 4168 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct
7 Correct 7082 ms 32868 KB Output is correct
8 Correct 7391 ms 32860 KB Output is correct
9 Correct 1038 ms 7324 KB Output is correct
10 Correct 3333 ms 31648 KB Output is correct
11 Correct 4240 ms 31260 KB Output is correct
12 Correct 893 ms 20340 KB Output is correct
13 Correct 1451 ms 20680 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1513 ms 7240 KB Output is correct
2 Correct 1482 ms 7224 KB Output is correct
3 Correct 1169 ms 7244 KB Output is correct
4 Correct 1042 ms 7376 KB Output is correct
5 Correct 1523 ms 4168 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct
7 Correct 7129 ms 76860 KB Output is correct
8 Correct 7422 ms 77016 KB Output is correct
9 Correct 1116 ms 7008 KB Output is correct
10 Correct 4457 ms 76660 KB Output is correct
11 Correct 5271 ms 77036 KB Output is correct
12 Correct 5400 ms 76844 KB Output is correct
13 Correct 4848 ms 76228 KB Output is correct
14 Correct 4851 ms 75712 KB Output is correct
15 Correct 5029 ms 75992 KB Output is correct
16 Correct 1 ms 4432 KB Output is correct
17 Correct 2576 ms 75912 KB Output is correct
18 Correct 1495 ms 46464 KB Output is correct
19 Correct 4767 ms 75596 KB Output is correct
20 Correct 4996 ms 75632 KB Output is correct
21 Correct 1 ms 4432 KB Output is correct
22 Correct 1 ms 4432 KB Output is correct
23 Correct 4749 ms 74924 KB Output is correct
24 Correct 2519 ms 75680 KB Output is correct
25 Correct 1441 ms 46460 KB Output is correct
26 Correct 7082 ms 32868 KB Output is correct
27 Correct 7391 ms 32860 KB Output is correct
28 Correct 1038 ms 7324 KB Output is correct
29 Correct 3333 ms 31648 KB Output is correct
30 Correct 4240 ms 31260 KB Output is correct
31 Correct 893 ms 20340 KB Output is correct
32 Correct 1451 ms 20680 KB Output is correct
33 Execution timed out 10051 ms 76796 KB Time limit exceeded
34 Halted 0 ms 0 KB -