oj.uz

Submission #724053

# Submission time Handle Problem Language Result Execution time Memory
724053 2023-04-14T16:17:45 Z sysia Road Construction (JOI21_road_construction) C++17
38 / 100
 10000 ms 187264 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--;
    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;
    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]){
                    if (i <= j) continue;
                    int x = abs(p2[i].first - p2[j].first) + abs(p2[i].second - p2[j].second);
                    ret.emplace_back(x);
                }
            }
        }
    }
    while (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);

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

    return 0;
}

Compilation message

road_construction.cpp: In function 'void solve()':
road_construction.cpp:124:23: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  124 |     while (ret.size() < k) ret.emplace_back(d+1);
      |            ~~~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7088 KB Output is correct
2 Correct 86 ms 7048 KB Output is correct
3 Correct 55 ms 5176 KB Output is correct
4 Correct 54 ms 5240 KB Output is correct
5 Correct 71 ms 4036 KB Output is correct
6 Correct 15 ms 728 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6898 ms 99712 KB Output is correct
2 Correct 6859 ms 99812 KB Output is correct
3 Correct 53 ms 5040 KB Output is correct
4 Correct 7248 ms 187264 KB Output is correct
5 Correct 6898 ms 74884 KB Output is correct
6 Correct 6803 ms 74976 KB Output is correct
7 Correct 6813 ms 68344 KB Output is correct

Subtask #3
0 / 7.0

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

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7088 KB Output is correct
2 Correct 86 ms 7048 KB Output is correct
3 Correct 55 ms 5176 KB Output is correct
4 Correct 54 ms 5240 KB Output is correct
5 Correct 71 ms 4036 KB Output is correct
6 Correct 15 ms 728 KB Output is correct
7 Correct 4303 ms 43348 KB Output is correct
8 Correct 4432 ms 43372 KB Output is correct
9 Correct 55 ms 5304 KB Output is correct
10 Correct 3936 ms 88932 KB Output is correct
11 Correct 3648 ms 93288 KB Output is correct
12 Correct 2054 ms 35292 KB Output is correct
13 Correct 2469 ms 57608 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 7088 KB Output is correct
2 Correct 86 ms 7048 KB Output is correct
3 Correct 55 ms 5176 KB Output is correct
4 Correct 54 ms 5240 KB Output is correct
5 Correct 71 ms 4036 KB Output is correct
6 Correct 15 ms 728 KB Output is correct
7 Correct 6898 ms 99712 KB Output is correct
8 Correct 6859 ms 99812 KB Output is correct
9 Correct 53 ms 5040 KB Output is correct
10 Correct 7248 ms 187264 KB Output is correct
11 Correct 6898 ms 74884 KB Output is correct
12 Correct 6803 ms 74976 KB Output is correct
13 Correct 6813 ms 68344 KB Output is correct
14 Execution timed out 10017 ms 57440 KB Time limit exceeded
15 Halted 0 ms 0 KB -