oj.uz

Submission #724058

# Submission time Handle Problem Language Result Execution time Memory
724058 2023-04-14T16:29:47 Z sysia Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 58656 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

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);
    }
};

#define int long long
typedef pair<int, int> T;
const int oo2 = 1e9+7;

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, int8_t>>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, -1);
            sweep.emplace_back(y+m, x, +1);
            sweep.emplace_back(y, 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, x, what]: sweep){
            if (what == 0){
                t.update(get(x));
            } else {
                all += what * t.query(get(x-m), get(x+m));
            }
        }
        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;
    }
    d--;
    set<T>ss;
    vector<int>ret;
    sort(p2.begin(), p2.end());
    int j = 0;
    for (int i = 0; i<n; i++){
        auto [x, y] = p2[i];
        while (j < i && p2[i].first - p2[j].first > d) {
            ss.erase({p2[j].second, p2[j].first});
            j++;
        }
        for (auto it = ss.lower_bound({y-d, x}); it != ss.upper_bound({y+d, x}); it++){
            ret.emplace_back(abs(x-it->second) + abs(y - it->first));
        }
        ss.insert({y, x});
    }
    while ((int)ret.size() < k) ret.emplace_back(d+1);
    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);

    solve();

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 6120 KB Output is correct
2 Correct 95 ms 6160 KB Output is correct
3 Correct 56 ms 5176 KB Output is correct
4 Correct 55 ms 5132 KB Output is correct
5 Correct 59 ms 4056 KB Output is correct
6 Correct 14 ms 604 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6666 ms 58628 KB Output is correct
2 Correct 6616 ms 58624 KB Output is correct
3 Correct 50 ms 4976 KB Output is correct
4 Correct 6866 ms 58368 KB Output is correct
5 Correct 6757 ms 58656 KB Output is correct
6 Correct 6690 ms 58632 KB Output is correct
7 Correct 6737 ms 57860 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 6120 KB Output is correct
2 Correct 95 ms 6160 KB Output is correct
3 Correct 56 ms 5176 KB Output is correct
4 Correct 55 ms 5132 KB Output is correct
5 Correct 59 ms 4056 KB Output is correct
6 Correct 14 ms 604 KB Output is correct
7 Correct 4483 ms 25936 KB Output is correct
8 Correct 4769 ms 25928 KB Output is correct
9 Correct 57 ms 5144 KB Output is correct
10 Correct 3865 ms 25408 KB Output is correct
11 Correct 3600 ms 25164 KB Output is correct
12 Correct 2092 ms 25924 KB Output is correct
13 Correct 2493 ms 24400 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 6120 KB Output is correct
2 Correct 95 ms 6160 KB Output is correct
3 Correct 56 ms 5176 KB Output is correct
4 Correct 55 ms 5132 KB Output is correct
5 Correct 59 ms 4056 KB Output is correct
6 Correct 14 ms 604 KB Output is correct
7 Correct 6666 ms 58628 KB Output is correct
8 Correct 6616 ms 58624 KB Output is correct
9 Correct 50 ms 4976 KB Output is correct
10 Correct 6866 ms 58368 KB Output is correct
11 Correct 6757 ms 58656 KB Output is correct
12 Correct 6690 ms 58632 KB Output is correct
13 Correct 6737 ms 57860 KB Output is correct
14 Execution timed out 10068 ms 57468 KB Time limit exceeded
15 Halted 0 ms 0 KB -