oj.uz

Submission #1111956

# Submission time Handle Problem Language Result Execution time Memory
1111956 2024-11-13T12:47:25 Z onbert Road Construction (JOI21_road_construction) C++17
6 / 100
 10000 ms 147352 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, maxN = 1e6 + 5, INF = 2e9 + 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;
    if (l<=target && target<=mid) {
        pt++;
        seg[pt] = seg[seg[id].lpt];
        seg[id].lpt = pt;
        update(pt, l, mid, target);
    }
    if (mid+1<=target && target<=r) {
        pt++;
        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;
    // cout << val << " " << x << endl;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1793 ms 9272 KB Output is correct
2 Correct 1745 ms 9284 KB Output is correct
3 Execution timed out 10046 ms 8960 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8584 ms 144240 KB Output is correct
2 Correct 8816 ms 146976 KB Output is correct
3 Correct 1269 ms 9176 KB Output is correct
4 Correct 5242 ms 146944 KB Output is correct
5 Correct 6356 ms 146764 KB Output is correct
6 Correct 6582 ms 147352 KB Output is correct
7 Correct 5819 ms 146348 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6124 ms 142908 KB Output is correct
2 Correct 5843 ms 142828 KB Output is correct
3 Execution timed out 10044 ms 4432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6124 ms 142908 KB Output is correct
2 Correct 5843 ms 142828 KB Output is correct
3 Execution timed out 10044 ms 4432 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1793 ms 9272 KB Output is correct
2 Correct 1745 ms 9284 KB Output is correct
3 Execution timed out 10046 ms 8960 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1793 ms 9272 KB Output is correct
2 Correct 1745 ms 9284 KB Output is correct
3 Execution timed out 10046 ms 8960 KB Time limit exceeded
4 Halted 0 ms 0 KB -