oj.uz

Submission #1110360

# Submission time Handle Problem Language Result Execution time Memory
1110360 2024-11-09T10:21:39 Z onbert Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 963292 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 250005, INF = 1e10;
struct pt {
    int x, y, lcnt, rcnt, cur, id;
    bool operator < (const pt &b) const {
        return x + y < b.x + b.y;
    }
};
struct thing {
    int id, plus, l, r, delta;
    bool operator < (const thing &b) const {
        return plus < b.plus;
    }
};
int n, k;

int fen[maxn];
vector<int> sub;
int dcl(int x) {return lower_bound(sub.begin(), sub.end(), x) - sub.begin();}
int dcr(int x) {return upper_bound(sub.begin(), sub.end(), x) - sub.begin() - 1;}

void update(int id, int len) {
    while (id <= len) {
        fen[id]++;
        id += (id & -id);
    }
}
int sum(int id) {
    int val = 0;
    while (id >= 1) {
        val += fen[id];
        id -= (id & -id);
    }
    return val;
}

void cunt(vector<pt> &vec, int dist, int sgn) {
    int sz = vec.size();
    sub = {-INF};
    for (auto &[x, y, lcnt, rcnt, cur, id]:vec) sub.push_back(x - y);
    sort(sub.begin(), sub.end()); sub.erase(unique(sub.begin(), sub.end()), sub.end());
    int len = sub.size();
    for (int i=0;i<=len;i++) fen[i] = 0;
    vector<thing> qry;
    for (int i=0;i<sz;i++) {
        auto [x, y, lcnt, rcnt, cur, id] = vec[i];
        qry.push_back({i, x + y - dist - 1, dcl(x - y - dist), dcr(x - y + dist), -1});
        qry.push_back({i, x + y + dist, dcl(x - y - dist), dcr(x - y + dist), 1});
    }
    sort(qry.begin(), qry.end());
    int pter = 0;
    for (int i=0;i<sz;i++) {
        // cout << i << " " << pter << endl;
        auto [x, y, lcnt, rcnt, cur, id] = vec[i];
        while (pter < sz*2 && qry[pter].plus < x + y) {
            vec[qry[pter].id].cur += (sum(qry[pter].r) - sum(qry[pter].l - 1)) * qry[pter].delta * sgn;
            pter++;
        }
        update(dcl(x - y), len);
    }
    while (pter < sz*2) {
        vec[qry[pter].id].cur += (sum(qry[pter].r) - sum(qry[pter].l - 1)) * qry[pter].delta * sgn;
        pter++;
    }
}

vector<pair<int,int>> cnt[maxn];
void solve(int l, int r, vector<pt> &vec) {
    if (l==r) return;
    // if (l==1 && r==1) for (auto [x, y, lcnt, rcnt, cur]:vec) cout << x << " " << y << " " << lcnt << " " << rcnt << endl;
    // if (l==1 && r==1) exit(0);
    int mid = (l+r)/2;
    cunt(vec, mid, 1);
    cunt(vec, l-1, -1);
    vector<pt> L, R;
    int total = 0;
    // if (mid == 4) cout << vec.size() << " " << l << " " << r << endl;
    // cout << l << " " << mid << " " << r << " " << vec.size() << endl;
    for (auto &[x, y, lcnt, rcnt, cur, id]:vec) {
        cur += lcnt;
        cnt[id].push_back({mid, cur});
        // if (id == 0) cout << "test " << l << " " << mid << " " << r << " " << cur << endl;
        total += cur;
        if (cur != lcnt) L.push_back({x, y, lcnt, cur, 0, id});
        if (cur != rcnt) R.push_back({x, y, cur, rcnt, 0, id});
    }
    // cout << "L\n";
    // for (auto [x, y, lcnt, rcnt, cur]:L) cout << x << " " << y << " " << lcnt << " " << rcnt << " " << cur << endl;
    // cout << "R\n";
    // for (auto [x, y, lcnt, rcnt, cur]:R) cout << x << " " << y << " " << lcnt << " " << rcnt << " " << cur << endl;
    if (L.size()) solve(l, mid, L);
    if (R.size() && total < 2*k) solve(mid+1, r, R);
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    vector<pt> vec(n);
    for (auto &[x, y, lcnt, rcnt, cur, id]:vec) cin >> x >> y, lcnt = 0, rcnt = n-1;
    sort(vec.begin(), vec.end());
    for (int i=0;i<n;i++) vec[i].id = i;
    // for (auto &[x, y, lcnt, rcnt, cur]:vec) cout << x << " " << y << " " << cur << endl;
    solve(1, INF, vec);

    map<int,int> mp;
    for (int i=0;i<n;i++) {
        sort(cnt[i].begin(), cnt[i].end());
        // cout << "test " << vec[i].x << " " << vec[i].y << endl;
        for (int j=0;j<cnt[i].size();j++) {
            bool kill = false;
            if (cnt[i][j].second == n-1) kill = true;
            int freq = cnt[i][j].second;
            if (j>0) freq -= cnt[i][j-1].second;
            mp[cnt[i][j].first] += freq;
            // cout << cnt[i][j].first << " " << freq << endl;
            if (kill) break;
        }
        // cout << "test " << vec[i].x << " " << vec[i].y << endl;
        // for (auto [dist, freq]:cnt[i]) if (dist<=12) cout << dist << " " << freq << endl;
    }
    int pos = 0;
    for (auto [dist, freq]:mp) {
        freq /= 2;
        for (int i=0;i<freq;i++) {
            pos++;
            cout << dist << '\n';
            if (pos == k) break;
        }
        if (pos == k) break;
    }
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:111:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |         for (int j=0;j<cnt[i].size();j++) {
      |                      ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7342 ms 389648 KB Output is correct
2 Correct 7282 ms 387716 KB Output is correct
3 Correct 7388 ms 395112 KB Output is correct
4 Correct 7479 ms 403908 KB Output is correct
5 Correct 2029 ms 80600 KB Output is correct
6 Correct 16 ms 9760 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9128 ms 879144 KB Output is correct
2 Correct 9289 ms 880368 KB Output is correct
3 Correct 6474 ms 379368 KB Output is correct
4 Correct 5983 ms 803572 KB Output is correct
5 Correct 8917 ms 927464 KB Output is correct
6 Correct 9036 ms 936480 KB Output is correct
7 Correct 8855 ms 963292 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4801 ms 398416 KB Output is correct
2 Correct 4851 ms 414600 KB Output is correct
3 Correct 3 ms 6736 KB Output is correct
4 Correct 6619 ms 897588 KB Output is correct
5 Correct 6677 ms 806388 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4801 ms 398416 KB Output is correct
2 Correct 4851 ms 414600 KB Output is correct
3 Correct 3 ms 6736 KB Output is correct
4 Correct 6619 ms 897588 KB Output is correct
5 Correct 6677 ms 806388 KB Output is correct
6 Correct 5012 ms 414576 KB Output is correct
7 Correct 4975 ms 412740 KB Output is correct
8 Correct 2 ms 6736 KB Output is correct
9 Correct 2 ms 6736 KB Output is correct
10 Correct 4770 ms 392568 KB Output is correct
11 Correct 6523 ms 896560 KB Output is correct
12 Correct 6724 ms 806072 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7342 ms 389648 KB Output is correct
2 Correct 7282 ms 387716 KB Output is correct
3 Correct 7388 ms 395112 KB Output is correct
4 Correct 7479 ms 403908 KB Output is correct
5 Correct 2029 ms 80600 KB Output is correct
6 Correct 16 ms 9760 KB Output is correct
7 Execution timed out 10061 ms 525748 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7342 ms 389648 KB Output is correct
2 Correct 7282 ms 387716 KB Output is correct
3 Correct 7388 ms 395112 KB Output is correct
4 Correct 7479 ms 403908 KB Output is correct
5 Correct 2029 ms 80600 KB Output is correct
6 Correct 16 ms 9760 KB Output is correct
7 Correct 9128 ms 879144 KB Output is correct
8 Correct 9289 ms 880368 KB Output is correct
9 Correct 6474 ms 379368 KB Output is correct
10 Correct 5983 ms 803572 KB Output is correct
11 Correct 8917 ms 927464 KB Output is correct
12 Correct 9036 ms 936480 KB Output is correct
13 Correct 8855 ms 963292 KB Output is correct
14 Correct 4801 ms 398416 KB Output is correct
15 Correct 4851 ms 414600 KB Output is correct
16 Correct 3 ms 6736 KB Output is correct
17 Correct 6619 ms 897588 KB Output is correct
18 Correct 6677 ms 806388 KB Output is correct
19 Correct 5012 ms 414576 KB Output is correct
20 Correct 4975 ms 412740 KB Output is correct
21 Correct 2 ms 6736 KB Output is correct
22 Correct 2 ms 6736 KB Output is correct
23 Correct 4770 ms 392568 KB Output is correct
24 Correct 6523 ms 896560 KB Output is correct
25 Correct 6724 ms 806072 KB Output is correct
26 Execution timed out 10061 ms 525748 KB Time limit exceeded
27 Halted 0 ms 0 KB -