oj.uz

Submission #724035

# Submission time Handle Problem Language Result Execution time Memory
724035 2023-04-14T15:51:29 Z sysia Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 160632 KB 
//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

struct Tree{
    vector<int>tab;
    int size = 1;

    Tree(int n){
        while (size < n) size*=2;
        tab.assign(2*size, 0);
    }

    void update(int x){
        x += size;
        while (x){
            tab[x]++;
            x/=2;
        }
    }

    int query(int l, int r){
        int ans = 0;
        for (l += size-1, r += size+1; r-l>1; l/=2, r/=2){
            if (!(l&1)) ans += tab[l+1];
            if (r&1) ans += tab[r-1];
        }
        return ans;
    }
};

void solve(){
    int n, k; cin >> n >> k;
    vector<T>p(n), p2;
    for (auto &[xx, yy]: p) {
        int x, y; cin >> x >> y;
        xx = x+y;
        yy = y-x;
        p2.emplace_back(x, y);
    }
    auto check = [&](int m){
        // debug(p);
        vector<tuple<int, int, int, int>>sweep;
        vector<int>s;
        for (auto [x, y]: p){
            sweep.emplace_back(y-m, x-m, x+m, -1);
            sweep.emplace_back(y+m, x-m, x+m, +1);
            sweep.emplace_back(y, x, x, 0);
            s.emplace_back(x-m);
            s.emplace_back(x);
            s.emplace_back(x+m);
        }
        sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        int M = (int)s.size();
        Tree t(M+2);
        auto get = [&](int x)->int {
            return lower_bound(s.begin(), s.end(), x) - s.begin();
        };
        sort(sweep.begin(), sweep.end());
        int all = 0;
        for (auto [y, l, r, what]: sweep){
            // debug(y, get(l), get(r), what);
            if (what == 0){
                t.update(get(l));
            } else {
                // debug(what * t.query(get(l), get(r)));
                all += what * t.query(get(l), get(r));
            }
        }
        
        all -= n;
        all/=2;
        debug(m, all);
        return (all >= k);
    };
    int l = 1, r = oo2 * 3;
    int d = oo2 * 3;
    while (r >= l){
        int m = (l+r)/2;
        if (check(m)){
            d = m;
            r = m-1;
        } else l = m+1;
    }
    debug(d);
    map<T, vector<int>>cnt;
    for (int i = 0; i<n; i++){
        cnt[{p2[i].first/d, p2[i].second/d}].emplace_back(i);
    }
    vector<int>X = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
    vector<int>Y = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
    vector<int>ret;
    auto dist = [&](int a, int b){
        if (a <= b) return;
        debug(a, b);
        ret.emplace_back(abs(p2[a].first - p2[b].first) + abs(p2[a].second - p2[b].second));
    };
    for (auto [coord, vec]: cnt){
        for (auto i: vec){
            for (int rep = 0; rep < 9; rep++){
                T now = {coord.first + X[rep], coord.second + Y[rep]};
                for (auto j: cnt[now]){
                    dist(i, j);
                }
            }
        }
    }
    sort(ret.begin(), ret.end());
    for (int i = 0; i<k; i++) cout << ret[i] << "\n";
}

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7012 KB Output is correct
2 Correct 88 ms 7080 KB Output is correct
3 Correct 55 ms 5040 KB Output is correct
4 Correct 55 ms 5144 KB Output is correct
5 Correct 65 ms 4004 KB Output is correct
6 Correct 16 ms 596 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8611 ms 73368 KB Output is correct
2 Correct 8958 ms 73340 KB Output is correct
3 Correct 54 ms 4916 KB Output is correct
4 Correct 9170 ms 160632 KB Output is correct
5 Correct 8064 ms 64532 KB Output is correct
6 Correct 8183 ms 64580 KB Output is correct
7 Correct 8147 ms 64468 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #4
0 / 20.0

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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7012 KB Output is correct
2 Correct 88 ms 7080 KB Output is correct
3 Correct 55 ms 5040 KB Output is correct
4 Correct 55 ms 5144 KB Output is correct
5 Correct 65 ms 4004 KB Output is correct
6 Correct 16 ms 596 KB Output is correct
7 Correct 5325 ms 35524 KB Output is correct
8 Correct 5337 ms 35628 KB Output is correct
9 Correct 55 ms 5164 KB Output is correct
10 Correct 4949 ms 78572 KB Output is correct
11 Correct 4510 ms 82948 KB Output is correct
12 Correct 2478 ms 29588 KB Output is correct
13 Correct 2876 ms 56020 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7012 KB Output is correct
2 Correct 88 ms 7080 KB Output is correct
3 Correct 55 ms 5040 KB Output is correct
4 Correct 55 ms 5144 KB Output is correct
5 Correct 65 ms 4004 KB Output is correct
6 Correct 16 ms 596 KB Output is correct
7 Correct 8611 ms 73368 KB Output is correct
8 Correct 8958 ms 73340 KB Output is correct
9 Correct 54 ms 4916 KB Output is correct
10 Correct 9170 ms 160632 KB Output is correct
11 Correct 8064 ms 64532 KB Output is correct
12 Correct 8183 ms 64580 KB Output is correct
13 Correct 8147 ms 64468 KB Output is correct
14 Execution timed out 10082 ms 64544 KB Time limit exceeded
15 Halted 0 ms 0 KB -