oj.uz

Submission #1111969

# Submission time Handle Problem Language Result Execution time Memory
1111969 2024-11-13T13:03:50 Z onbert Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 145852 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, INF = 4e9 + 10;
int n, k;
pair<int,int> a[maxn];
int sz;
vector<int> vals = {-INF};
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[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)/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 1873 ms 9288 KB Output is correct
2 Correct 1784 ms 9256 KB Output is correct
3 Correct 1323 ms 9288 KB Output is correct
4 Correct 1235 ms 9500 KB Output is correct
5 Correct 1636 ms 8188 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 8916 ms 144028 KB Output is correct
2 Correct 8672 ms 144300 KB Output is correct
3 Correct 1342 ms 9324 KB Output is correct
4 Correct 5096 ms 143620 KB Output is correct
5 Correct 6344 ms 143812 KB Output is correct
6 Correct 6441 ms 143836 KB Output is correct
7 Correct 5707 ms 143200 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6705 ms 142904 KB Output is correct
2 Correct 6349 ms 142660 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2982 ms 144368 KB Output is correct
5 Correct 1766 ms 87080 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6705 ms 142904 KB Output is correct
2 Correct 6349 ms 142660 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2982 ms 144368 KB Output is correct
5 Correct 1766 ms 87080 KB Output is correct
6 Correct 5995 ms 143872 KB Output is correct
7 Correct 6229 ms 145852 KB Output is correct
8 Correct 2 ms 4432 KB Output is correct
9 Correct 1 ms 4444 KB Output is correct
10 Correct 5818 ms 141520 KB Output is correct
11 Correct 2986 ms 144752 KB Output is correct
12 Correct 1709 ms 90004 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1873 ms 9288 KB Output is correct
2 Correct 1784 ms 9256 KB Output is correct
3 Correct 1323 ms 9288 KB Output is correct
4 Correct 1235 ms 9500 KB Output is correct
5 Correct 1636 ms 8188 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct
7 Execution timed out 10040 ms 59656 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1873 ms 9288 KB Output is correct
2 Correct 1784 ms 9256 KB Output is correct
3 Correct 1323 ms 9288 KB Output is correct
4 Correct 1235 ms 9500 KB Output is correct
5 Correct 1636 ms 8188 KB Output is correct
6 Correct 5 ms 4688 KB Output is correct
7 Correct 8916 ms 144028 KB Output is correct
8 Correct 8672 ms 144300 KB Output is correct
9 Correct 1342 ms 9324 KB Output is correct
10 Correct 5096 ms 143620 KB Output is correct
11 Correct 6344 ms 143812 KB Output is correct
12 Correct 6441 ms 143836 KB Output is correct
13 Correct 5707 ms 143200 KB Output is correct
14 Correct 6705 ms 142904 KB Output is correct
15 Correct 6349 ms 142660 KB Output is correct
16 Correct 1 ms 4432 KB Output is correct
17 Correct 2982 ms 144368 KB Output is correct
18 Correct 1766 ms 87080 KB Output is correct
19 Correct 5995 ms 143872 KB Output is correct
20 Correct 6229 ms 145852 KB Output is correct
21 Correct 2 ms 4432 KB Output is correct
22 Correct 1 ms 4444 KB Output is correct
23 Correct 5818 ms 141520 KB Output is correct
24 Correct 2986 ms 144752 KB Output is correct
25 Correct 1709 ms 90004 KB Output is correct
26 Execution timed out 10040 ms 59656 KB Time limit exceeded
27 Halted 0 ms 0 KB -