oj.uz

Submission #1111958

# Submission time Handle Problem Language Result Execution time Memory
1111958 2024-11-13T12:50:57 Z onbert Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 148160 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, maxN = 1e6 + 5, INF = 4e9 + 10;
int n, k;
pair<int,int> a[maxn];
int sz;
vector<int> vals = {-(int)1e18};
int ldc(int x) {return lower_bound(vals.begin(), vals.end(), x) - vals.begin();}
int rdc(int x) {return upper_bound(vals.begin(), vals.end(), x) - vals.begin() - 1;}

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

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

pair<int,int> b[maxn];
node seg[18000000];
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)/2;
    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(int id, int dist) {
    int L = ldc(a[id].second - dist), R = rdc(a[id].second + dist);
    int val = qry(lg[id], 1, sz, L, R);
    int x = lower_bound(a+1, a+n+1, make_pair(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};
        int l = 1, r = INF;
        while (l < r) {
            int 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) {
        int 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;
        int l = dist+1, r = INF;
        while (l < r) {
            int mid = (l+r)/2;
            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 1761 ms 9216 KB Output is correct
2 Correct 1840 ms 9208 KB Output is correct
3 Correct 1339 ms 9380 KB Output is correct
4 Correct 1198 ms 3400 KB Output is correct
5 Correct 1656 ms 8192 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 8768 ms 145740 KB Output is correct
2 Correct 9151 ms 143880 KB Output is correct
3 Correct 1388 ms 9184 KB Output is correct
4 Correct 5559 ms 145864 KB Output is correct
5 Correct 6596 ms 144036 KB Output is correct
6 Correct 6476 ms 144112 KB Output is correct
7 Correct 5619 ms 143512 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5895 ms 144188 KB Output is correct
2 Correct 5842 ms 142908 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2894 ms 145844 KB Output is correct
5 Correct 1703 ms 94140 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5895 ms 144188 KB Output is correct
2 Correct 5842 ms 142908 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2894 ms 145844 KB Output is correct
5 Correct 1703 ms 94140 KB Output is correct
6 Correct 5658 ms 148160 KB Output is correct
7 Correct 5505 ms 148132 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 1 ms 4432 KB Output is correct
10 Correct 5477 ms 147448 KB Output is correct
11 Correct 2825 ms 146776 KB Output is correct
12 Correct 1753 ms 94012 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 9216 KB Output is correct
2 Correct 1840 ms 9208 KB Output is correct
3 Correct 1339 ms 9380 KB Output is correct
4 Correct 1198 ms 3400 KB Output is correct
5 Correct 1656 ms 8192 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Execution timed out 10034 ms 64596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1761 ms 9216 KB Output is correct
2 Correct 1840 ms 9208 KB Output is correct
3 Correct 1339 ms 9380 KB Output is correct
4 Correct 1198 ms 3400 KB Output is correct
5 Correct 1656 ms 8192 KB Output is correct
6 Correct 6 ms 4688 KB Output is correct
7 Correct 8768 ms 145740 KB Output is correct
8 Correct 9151 ms 143880 KB Output is correct
9 Correct 1388 ms 9184 KB Output is correct
10 Correct 5559 ms 145864 KB Output is correct
11 Correct 6596 ms 144036 KB Output is correct
12 Correct 6476 ms 144112 KB Output is correct
13 Correct 5619 ms 143512 KB Output is correct
14 Correct 5895 ms 144188 KB Output is correct
15 Correct 5842 ms 142908 KB Output is correct
16 Correct 1 ms 4432 KB Output is correct
17 Correct 2894 ms 145844 KB Output is correct
18 Correct 1703 ms 94140 KB Output is correct
19 Correct 5658 ms 148160 KB Output is correct
20 Correct 5505 ms 148132 KB Output is correct
21 Correct 2 ms 4432 KB Output is correct
22 Correct 1 ms 4432 KB Output is correct
23 Correct 5477 ms 147448 KB Output is correct
24 Correct 2825 ms 146776 KB Output is correct
25 Correct 1753 ms 94012 KB Output is correct
26 Execution timed out 10034 ms 64596 KB Time limit exceeded
27 Halted 0 ms 0 KB -