oj.uz

Submission #893463

# Submission time Handle Problem Language Result Execution time Memory
893463 2023-12-27T05:18:25 Z vjudge1 Road Construction (JOI21_road_construction) C++17
18 / 100
 1220 ms 106656 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()

template<class S, class T>
bool chmin(S &a, const T &b) {
    return a > b && (a = b) == b;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
    return a < b && (a = b) == b;
}
const int inf = 1e9 + 7;
const int INF = 1e18 + 7;
const int mod = 998244353;

map<int, int> mp;

struct Segment_Tree {
    int n;
    vector<int> t, modify;
    Segment_Tree(int n) {
        this->n = n;
        t.assign(4 * n, INF);
        modify.assign(4 * n, 0);
    }
    
    void push(int v, int tl, int tr) {
        t[v] += modify[v];
        if (tl != tr) {
            modify[v << 1] += modify[v];
            modify[v << 1 | 1] += modify[v];
        }
        modify[v] = 0;
    }
    
    void upd(int v, int tl, int tr, int l, int r, int x) {
        if (modify[v]) push(v, tl, tr);
        if (tl > r || tr < l) return;
        if (tl >= l && tr <= r) {
            modify[v] += x;
            push(v, tl, tr);
            return;
        }
        int tm = (tl + tr) >> 1;
        upd(v << 1, tl, tm, l, r, x);
        upd(v << 1 | 1, tm + 1, tr, l, r, x);
        t[v] = min(t[v << 1], t[v << 1 | 1]);
    } void upd(int l, int r, int x) {
        upd(1, 1, n, l, r, x);
    }
    
    void upd_pos(int v, int tl, int tr, int i, int x) {
        if (modify[v]) push(v, tl, tr);
        if (tl == tr) {
            t[v] = x;
            return;
        }
        int tm = (tl + tr) >> 1;
        if (tm >= i) upd_pos(v << 1, tl, tm, i, x);
        else upd_pos(v << 1 | 1, tm + 1, tr, i, x);
        t[v] = min(t[v << 1], t[v << 1 | 1]);
    } void upd_pos(int i, int x) {
        upd_pos(1, 1, n, i, x);
    }
    
    int get(int v, int tl, int tr, int l, int r) {
        if (modify[v]) push(v, tl, tr);
        if (tl > r || tr < l) return INF;
        if (tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return min(get(v << 1, tl, tm, l, r), get(v << 1 | 1, tm + 1, tr, l, r));
    } int get(int l, int r) {
        return get(1, 1, n, l, r);
    }
};

void compress(vector<int> &x, vector<int> &y, int n) {
    vector<int> v;
    for (int i = 0; i < n; ++i) {
        v.push_back(x[i]);
        v.push_back(y[i]);
    }
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    for (int i = 0; i < size(v); ++i) {
        mp[v[i]] = i + 1;
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vector<int> x(n), y(n);
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
    }
    auto dist = [&](int i, int j) {
        return abs(x[i] - x[j]) + abs(y[i] - y[j]);
    };
    if (k == 1) {
        compress(x, y, n);
        Segment_Tree s(2 * n), b(2 * n);
        vector<pair<int, int>> v;
        for (int i = 0; i < n; ++i) {
            v.push_back({x[i], y[i]});
        }
        sort(all(v));
        for (int i = 0; i < n; ++i) {
            x[i] = v[i].first, y[i] = v[i].second;
        }
        int res = abs(x[0] - x[1]) + abs(y[0] - y[1]);
        for (int i = 0; i < n; ++i) {
            s.upd(1, mp[y[i]], y[i] + x[i]);
            b.upd(mp[y[i]], 2 * n, -y[i] + x[i]);
            chmin(res, min(s.get(1, mp[y[i]]), b.get(mp[y[i]], 2 * n)));
            s.upd(1, mp[y[i]], -y[i] - x[i]);
            b.upd(mp[y[i]], 2 * n, y[i] - x[i]);
            s.upd_pos(mp[y[i]], -y[i] - x[i]);
            b.upd_pos(mp[y[i]], y[i] - x[i]);
        }
        cout << res;
    } else if (n <= 1000) {
        int d[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                d[i][j] = dist(i, j);
            }
        }
        for (int k = 0; k < n; ++k) {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    chmin(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        multiset<int> st;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                st.insert(d[i][j]);
                if (size(st) > k) {
                    st.erase(--st.end());
                }
            }
        }
        for (int i : st) {
            cout << i << '\n';
        }
    } else {
        sort(all(x));
        multiset<pair<int, int>> st;
        for (int i = 0; i + 1 < n; ++i) {
            st.insert({dist(i, i + 1), i + 1});
        }
        vector<int> res;
        while (size(res) < k) {
            auto [d, i] = *st.begin();
            st.erase(st.begin());
            res.push_back(d);
            if (i + 1 < n) {
                st.insert({d + dist(i, i + 1), i + 1});
            }
        }
        for (int i : res) {
            cout << i << '\n';
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 22608 KB Output is correct
2 Correct 803 ms 22620 KB Output is correct
3 Correct 338 ms 18516 KB Output is correct
4 Correct 340 ms 18768 KB Output is correct
5 Correct 780 ms 21596 KB Output is correct
6 Correct 651 ms 8280 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 326 ms 23144 KB Output is correct
2 Correct 327 ms 23236 KB Output is correct
3 Correct 316 ms 18432 KB Output is correct
4 Correct 147 ms 22924 KB Output is correct
5 Correct 142 ms 23116 KB Output is correct
6 Correct 145 ms 23236 KB Output is correct
7 Correct 150 ms 22408 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1220 ms 106504 KB Output is correct
2 Correct 1187 ms 106656 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 461 ms 90436 KB Output is correct
5 Correct 484 ms 75052 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1220 ms 106504 KB Output is correct
2 Correct 1187 ms 106656 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 461 ms 90436 KB Output is correct
5 Correct 484 ms 75052 KB Output is correct
6 Incorrect 174 ms 19976 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 22608 KB Output is correct
2 Correct 803 ms 22620 KB Output is correct
3 Correct 338 ms 18516 KB Output is correct
4 Correct 340 ms 18768 KB Output is correct
5 Correct 780 ms 21596 KB Output is correct
6 Correct 651 ms 8280 KB Output is correct
7 Incorrect 153 ms 12868 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 22608 KB Output is correct
2 Correct 803 ms 22620 KB Output is correct
3 Correct 338 ms 18516 KB Output is correct
4 Correct 340 ms 18768 KB Output is correct
5 Correct 780 ms 21596 KB Output is correct
6 Correct 651 ms 8280 KB Output is correct
7 Correct 326 ms 23144 KB Output is correct
8 Correct 327 ms 23236 KB Output is correct
9 Correct 316 ms 18432 KB Output is correct
10 Correct 147 ms 22924 KB Output is correct
11 Correct 142 ms 23116 KB Output is correct
12 Correct 145 ms 23236 KB Output is correct
13 Correct 150 ms 22408 KB Output is correct
14 Correct 1220 ms 106504 KB Output is correct
15 Correct 1187 ms 106656 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 461 ms 90436 KB Output is correct
18 Correct 484 ms 75052 KB Output is correct
19 Incorrect 174 ms 19976 KB Output isn't correct
20 Halted 0 ms 0 KB -