oj.uz

Submission #1111999

# Submission time Handle Problem Language Result Execution time Memory
1111999 2024-11-13T13:42:55 Z tosivanmak Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 80044 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];
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[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, 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 1532 ms 7240 KB Output is correct
2 Correct 1470 ms 7156 KB Output is correct
3 Correct 1136 ms 7320 KB Output is correct
4 Correct 993 ms 7376 KB Output is correct
5 Correct 1382 ms 6224 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 6967 ms 77636 KB Output is correct
2 Correct 7130 ms 77492 KB Output is correct
3 Correct 1114 ms 7124 KB Output is correct
4 Correct 4330 ms 77716 KB Output is correct
5 Correct 5124 ms 78604 KB Output is correct
6 Correct 5172 ms 77608 KB Output is correct
7 Correct 4611 ms 76780 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4900 ms 76676 KB Output is correct
2 Correct 5093 ms 76396 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2432 ms 77588 KB Output is correct
5 Correct 1411 ms 49732 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4900 ms 76676 KB Output is correct
2 Correct 5093 ms 76396 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 2432 ms 77588 KB Output is correct
5 Correct 1411 ms 49732 KB Output is correct
6 Correct 5015 ms 76896 KB Output is correct
7 Correct 5014 ms 77460 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 5040 ms 75776 KB Output is correct
11 Correct 2479 ms 76728 KB Output is correct
12 Correct 1412 ms 47672 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1532 ms 7240 KB Output is correct
2 Correct 1470 ms 7156 KB Output is correct
3 Correct 1136 ms 7320 KB Output is correct
4 Correct 993 ms 7376 KB Output is correct
5 Correct 1382 ms 6224 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct
7 Correct 7235 ms 32492 KB Output is correct
8 Correct 7215 ms 33808 KB Output is correct
9 Correct 1002 ms 7324 KB Output is correct
10 Correct 3220 ms 32524 KB Output is correct
11 Correct 4220 ms 32288 KB Output is correct
12 Correct 709 ms 20664 KB Output is correct
13 Correct 1490 ms 22476 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1532 ms 7240 KB Output is correct
2 Correct 1470 ms 7156 KB Output is correct
3 Correct 1136 ms 7320 KB Output is correct
4 Correct 993 ms 7376 KB Output is correct
5 Correct 1382 ms 6224 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct
7 Correct 6967 ms 77636 KB Output is correct
8 Correct 7130 ms 77492 KB Output is correct
9 Correct 1114 ms 7124 KB Output is correct
10 Correct 4330 ms 77716 KB Output is correct
11 Correct 5124 ms 78604 KB Output is correct
12 Correct 5172 ms 77608 KB Output is correct
13 Correct 4611 ms 76780 KB Output is correct
14 Correct 4900 ms 76676 KB Output is correct
15 Correct 5093 ms 76396 KB Output is correct
16 Correct 2 ms 4432 KB Output is correct
17 Correct 2432 ms 77588 KB Output is correct
18 Correct 1411 ms 49732 KB Output is correct
19 Correct 5015 ms 76896 KB Output is correct
20 Correct 5014 ms 77460 KB Output is correct
21 Correct 1 ms 4432 KB Output is correct
22 Correct 1 ms 4432 KB Output is correct
23 Correct 5040 ms 75776 KB Output is correct
24 Correct 2479 ms 76728 KB Output is correct
25 Correct 1412 ms 47672 KB Output is correct
26 Correct 7235 ms 32492 KB Output is correct
27 Correct 7215 ms 33808 KB Output is correct
28 Correct 1002 ms 7324 KB Output is correct
29 Correct 3220 ms 32524 KB Output is correct
30 Correct 4220 ms 32288 KB Output is correct
31 Correct 709 ms 20664 KB Output is correct
32 Correct 1490 ms 22476 KB Output is correct
33 Execution timed out 10105 ms 80044 KB Time limit exceeded
34 Halted 0 ms 0 KB -