oj.uz

Submission #1111962

# Submission time Handle Problem Language Result Execution time Memory
1111962 2024-11-13T12:54:12 Z onbert Road Construction (JOI21_road_construction) C++17
32 / 100
 10000 ms 210680 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];
vector<node> seg = {{0, 0, 0}};
vector<int> lg = {1};
void build(int id, int l, int r) {
    seg.push_back({0, 0, 0});
    if (l==r) return;
    int mid = (l+r) >> 1;
    seg[id].lpt = seg.size();
    build(seg.size(), l, mid);
    seg[id].rpt = seg.size();
    build(seg.size(), 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) {
        seg.push_back(seg[seg[id].lpt]);
        seg[id].lpt = seg.size() - 1;
        update(seg.size() - 1, l, mid, target);
    }
    if (mid+1<=target && target<=r) {
        seg.push_back(seg[seg[id].rpt]);
        seg[id].rpt = seg.size() - 1;
        update(seg.size() - 1, 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++) {
        seg.push_back(seg[lg.back()]);
        lg.push_back(seg.size() - 1);
        update(seg.size() - 1, 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();
        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 1804 ms 5560 KB Output is correct
2 Correct 1716 ms 5364 KB Output is correct
3 Correct 1362 ms 5456 KB Output is correct
4 Correct 1155 ms 5448 KB Output is correct
5 Correct 1690 ms 4516 KB Output is correct
6 Correct 5 ms 2848 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10060 ms 208552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6873 ms 208532 KB Output is correct
2 Correct 6786 ms 210576 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 3045 ms 208572 KB Output is correct
5 Correct 1671 ms 112032 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6873 ms 208532 KB Output is correct
2 Correct 6786 ms 210576 KB Output is correct
3 Correct 1 ms 2384 KB Output is correct
4 Correct 3045 ms 208572 KB Output is correct
5 Correct 1671 ms 112032 KB Output is correct
6 Correct 6762 ms 210680 KB Output is correct
7 Correct 6806 ms 209044 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1 ms 2384 KB Output is correct
10 Correct 6785 ms 210672 KB Output is correct
11 Correct 2991 ms 208484 KB Output is correct
12 Correct 1762 ms 112032 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1804 ms 5560 KB Output is correct
2 Correct 1716 ms 5364 KB Output is correct
3 Correct 1362 ms 5456 KB Output is correct
4 Correct 1155 ms 5448 KB Output is correct
5 Correct 1690 ms 4516 KB Output is correct
6 Correct 5 ms 2848 KB Output is correct
7 Execution timed out 10047 ms 63100 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1804 ms 5560 KB Output is correct
2 Correct 1716 ms 5364 KB Output is correct
3 Correct 1362 ms 5456 KB Output is correct
4 Correct 1155 ms 5448 KB Output is correct
5 Correct 1690 ms 4516 KB Output is correct
6 Correct 5 ms 2848 KB Output is correct
7 Execution timed out 10060 ms 208552 KB Time limit exceeded
8 Halted 0 ms 0 KB -