oj.uz

Submission #724043

# Submission time Handle Problem Language Result Execution time Memory
724043 2023-04-14T16:00:27 Z sysia Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 196060 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> s;
    Tree(){}
	Tree(int n) : s(n) {}
    void fit(int n){
        s.assign(n, 0);
    }
	void update(int pos) { // a[pos] += dif
		for (; pos < (int)s.size(); pos |= pos + 1) s[pos]++;
	}
	int query(int pos) { // sum of values in [0, pos)
		int res = 0;
		for (; pos > 0; pos &= pos - 1) res += s[pos-1];
		return res;
	}
	int query(int l, int r){
        return query(r+1) - query(l);
    }
};

void solve(){
    int n, k; cin >> n >> k;
    vector<T>p, p2(n);
    for (auto &[x, y]: p2) {
        cin >> x >> y;
        p.emplace_back(x+y, y-x);
    }
    vector<tuple<int, int, int, int>>sweep;
    vector<int>s;
    Tree t;
    auto check = [&](int m){
        // debug(p);
        sweep.clear();
        s.clear();
        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);
        }
        stable_sort(s.begin(), s.end());
        s.erase(unique(s.begin(), s.end()), s.end());
        int M = (int)s.size();
        t.fit(M+1);
        auto get = [&](int x)->int {
            return lower_bound(s.begin(), s.end(), x) - s.begin();
        };
        stable_sort(sweep.begin(), sweep.end());
        int all = 0;
        for (auto [y, l, r, what]: sweep){
            if (what == 0){
                t.update(get(l));
            } else {
                all += what * t.query(get(l), get(r));
            }
        }
        all -= n;
        all/=2;
        debug(m, all);
        return (all >= k);
    };
    int l = 1, r = oo2 * 2;
    int d = oo2 * 2;
    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 7144 KB Output is correct
2 Correct 85 ms 7092 KB Output is correct
3 Correct 53 ms 5184 KB Output is correct
4 Correct 58 ms 5196 KB Output is correct
5 Correct 58 ms 4132 KB Output is correct
6 Correct 15 ms 764 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7414 ms 108768 KB Output is correct
2 Correct 7593 ms 108672 KB Output is correct
3 Correct 56 ms 5120 KB Output is correct
4 Correct 7800 ms 196060 KB Output is correct
5 Correct 7605 ms 83800 KB Output is correct
6 Correct 7552 ms 83800 KB Output is correct
7 Correct 7850 ms 77276 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10096 ms 69348 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 10096 ms 69348 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 7144 KB Output is correct
2 Correct 85 ms 7092 KB Output is correct
3 Correct 53 ms 5184 KB Output is correct
4 Correct 58 ms 5196 KB Output is correct
5 Correct 58 ms 4132 KB Output is correct
6 Correct 15 ms 764 KB Output is correct
7 Correct 4811 ms 49364 KB Output is correct
8 Correct 4662 ms 49376 KB Output is correct
9 Correct 56 ms 5192 KB Output is correct
10 Correct 4312 ms 92264 KB Output is correct
11 Correct 4067 ms 96588 KB Output is correct
12 Correct 2410 ms 37548 KB Output is correct
13 Correct 2737 ms 68000 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 7144 KB Output is correct
2 Correct 85 ms 7092 KB Output is correct
3 Correct 53 ms 5184 KB Output is correct
4 Correct 58 ms 5196 KB Output is correct
5 Correct 58 ms 4132 KB Output is correct
6 Correct 15 ms 764 KB Output is correct
7 Correct 7414 ms 108768 KB Output is correct
8 Correct 7593 ms 108672 KB Output is correct
9 Correct 56 ms 5120 KB Output is correct
10 Correct 7800 ms 196060 KB Output is correct
11 Correct 7605 ms 83800 KB Output is correct
12 Correct 7552 ms 83800 KB Output is correct
13 Correct 7850 ms 77276 KB Output is correct
14 Execution timed out 10096 ms 69348 KB Time limit exceeded
15 Halted 0 ms 0 KB -