oj.uz

Submission #724022

# Submission time Handle Problem Language Result Execution time Memory
724022 2023-04-14T15:41:16 Z sysia Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 178552 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[{p[i].first/d, p[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 88 ms 7008 KB Output is correct
2 Correct 100 ms 6928 KB Output is correct
3 Correct 58 ms 5040 KB Output is correct
4 Correct 58 ms 5080 KB Output is correct
5 Correct 66 ms 4096 KB Output is correct
6 Correct 16 ms 612 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8569 ms 97704 KB Output is correct
2 Correct 8510 ms 97964 KB Output is correct
3 Correct 52 ms 4972 KB Output is correct
4 Correct 8616 ms 178552 KB Output is correct
5 Correct 8055 ms 69996 KB Output is correct
6 Correct 8260 ms 70144 KB Output is correct
7 Correct 8499 ms 67728 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10042 ms 69544 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 10042 ms 69544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7008 KB Output is correct
2 Correct 100 ms 6928 KB Output is correct
3 Correct 58 ms 5040 KB Output is correct
4 Correct 58 ms 5080 KB Output is correct
5 Correct 66 ms 4096 KB Output is correct
6 Correct 16 ms 612 KB Output is correct
7 Correct 5820 ms 31344 KB Output is correct
8 Correct 5725 ms 31324 KB Output is correct
9 Correct 63 ms 5156 KB Output is correct
10 Correct 5405 ms 81008 KB Output is correct
11 Correct 4506 ms 81116 KB Output is correct
12 Correct 2439 ms 31328 KB Output is correct
13 Correct 2797 ms 37040 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 7008 KB Output is correct
2 Correct 100 ms 6928 KB Output is correct
3 Correct 58 ms 5040 KB Output is correct
4 Correct 58 ms 5080 KB Output is correct
5 Correct 66 ms 4096 KB Output is correct
6 Correct 16 ms 612 KB Output is correct
7 Correct 8569 ms 97704 KB Output is correct
8 Correct 8510 ms 97964 KB Output is correct
9 Correct 52 ms 4972 KB Output is correct
10 Correct 8616 ms 178552 KB Output is correct
11 Correct 8055 ms 69996 KB Output is correct
12 Correct 8260 ms 70144 KB Output is correct
13 Correct 8499 ms 67728 KB Output is correct
14 Execution timed out 10042 ms 69544 KB Time limit exceeded
15 Halted 0 ms 0 KB -