oj.uz

Submission #1079960

# Submission time Handle Problem Language Result Execution time Memory
1079960 2024-08-29T05:03:17 Z nathan4690 Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 41016 KB 
// The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
// Spring Training Camp/Qualifying Trial
// March 20–23, 2021 (Komaba, Tokyo)
// Contest Day 2 – Road Construction
// JOI21_road_construction
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define pll pair<ll,ll>
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
#define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

struct Segment{
    ll a, b1, b2, sgn, idx;
    Segment(){}
    Segment(ll a, ll b1, ll b2, ll sgn, ll idx): a(a), b1(b1), b2(b2), sgn(sgn), idx(idx){}
    bool operator<(const Segment &rhs) const{
        return a < rhs.a;
    }
};

struct FenwickTree{
    int n;
    vector<int> bit;
    FenwickTree(){}
    FenwickTree(int n): n(n), bit(n+1, 0){}
    void update(int idx, int v){
        if(idx <= 0) return;
        for(;idx<=n;idx+=(idx&-idx)) bit[idx]+=v;
    }
    long long getSum(int idx){
        if(idx <= 0) return 0;
        int res = 0;
        for(;idx;idx-=idx&-idx) res += bit[idx];
        return res;
    }
};

ll n,k, L, R, mid, cnt[maxn];
pair<ll,ll> p[maxn];
vector<Segment> all;
vector<ll> values;
FenwickTree fen;

bool check(ll x){
    all.clear();
    values.clear();
    values.push_back(-inf);
    f1(i,n){
        cnt[i] = 0;
        all.push_back(Segment(p[i].first - x - 1, p[i].second - x, p[i].second + x, -1, i));
        all.push_back(Segment(p[i].first + x, p[i].second - x, p[i].second + x, 1, i));
        values.push_back(all.back().b1);
        values.push_back(all.back().b2);
        values.push_back(p[i].second);
    }
    fen = FenwickTree(3*n);
    sort(values.begin(), values.end());
    sort(all.begin(), all.end());
    // S.clear();
    ll ptr = 1;
    for(Segment item: all){
        while(p[ptr].first <= item.a){
            // S.insert({p[ptr].second, ptr});
            ll ptr_x = lower_bound(values.begin(), values.end(), p[ptr].second) - values.begin();
            fen.update(ptr_x, 1);
            ptr++;
        }
        ll ptr_r = lower_bound(values.begin(), values.end(), item.b2) - values.begin();
        ll ptr_l = lower_bound(values.begin(), values.end(), item.b1) - values.begin();
        cnt[item.idx] += (fen.getSum(ptr_r) - fen.getSum(ptr_l - 1)) * item.sgn;
    }
    ll tot = 0;
    f1(i,n) tot += cnt[i];
    tot -= n;
    // cout << x << ' ' << tot;el;
    tot /= 2;
    return tot >= k;
}

set<pair<ll,ll>> S2;
vector<ll> allDist;

void addPath(ll idx1, ll idx2){
    allDist.push_back(max(abs(p[idx1].first - p[idx2].first), abs(p[idx1].second - p[idx2].second)));
}

void getAllLess(ll x){
    S2.clear();
    ll ptr_l = 1, ptr_r = 1;
    f1(i,n){
        ll a1 = p[i].first - x, a2 = p[i].first + x;
        while(p[ptr_r].first <= a2){
            S2.insert({p[ptr_r].second, ptr_r});
            ptr_r++;
        }
        while(p[ptr_l].first < a1){
            S2.erase({p[ptr_l].second, ptr_l});
            ptr_l++;
        }
        ll b1 = p[i].second - x, b2 = p[i].second + x;
        auto it1 = S2.lower_bound({b1, 0});
        auto it2 = S2.lower_bound({b2, inf});
        while(it1 != it2){
            ll idx = (*it1).second;
            if(idx < i) addPath(idx, i);
            it1++;
        }
    }
}

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

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> k;
    f1(i,n) {
        ll x, y;
        cin >> x >> y;
        p[i] = {x-y,x+y};
    }
    p[n+1] = {inf, inf};
    sort(p+1,p+n+1);
    L = 0; R = 4e9;
    while(L <= R){
        mid = (L + R) / 2;
        if(check(mid)) R = mid-1;
        else L = mid+1;
    }
    getAllLess(L-1);
    sort(allDist.begin(), allDist.end());
    for(ll item: allDist) cout << item << '\n';
    for(ll i=allDist.size() + 1;i<=k;i++) cout << L << '\n';
    return 0;
}

Compilation message

road_construction.cpp: In function 'int main()':
road_construction.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
road_construction.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5292 KB Output is correct
2 Correct 58 ms 5312 KB Output is correct
3 Correct 50 ms 5312 KB Output is correct
4 Correct 47 ms 5316 KB Output is correct
5 Correct 51 ms 4032 KB Output is correct
6 Correct 10 ms 604 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4061 ms 41016 KB Output is correct
2 Correct 4166 ms 41016 KB Output is correct
3 Correct 50 ms 5068 KB Output is correct
4 Correct 3978 ms 40888 KB Output is correct
5 Correct 3890 ms 41012 KB Output is correct
6 Correct 3955 ms 41012 KB Output is correct
7 Correct 3937 ms 40248 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8427 ms 39812 KB Output is correct
2 Correct 8578 ms 39896 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3695 ms 39800 KB Output is correct
5 Correct 7135 ms 39888 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8427 ms 39812 KB Output is correct
2 Correct 8578 ms 39896 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 3695 ms 39800 KB Output is correct
5 Correct 7135 ms 39888 KB Output is correct
6 Correct 8568 ms 39860 KB Output is correct
7 Correct 8545 ms 40000 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 8633 ms 39924 KB Output is correct
11 Correct 3853 ms 39860 KB Output is correct
12 Correct 7098 ms 39884 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5292 KB Output is correct
2 Correct 58 ms 5312 KB Output is correct
3 Correct 50 ms 5312 KB Output is correct
4 Correct 47 ms 5316 KB Output is correct
5 Correct 51 ms 4032 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 3795 ms 20936 KB Output is correct
8 Correct 3748 ms 20952 KB Output is correct
9 Correct 51 ms 5312 KB Output is correct
10 Correct 3360 ms 20188 KB Output is correct
11 Correct 3149 ms 20184 KB Output is correct
12 Correct 1787 ms 18904 KB Output is correct
13 Correct 2542 ms 19404 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 5292 KB Output is correct
2 Correct 58 ms 5312 KB Output is correct
3 Correct 50 ms 5312 KB Output is correct
4 Correct 47 ms 5316 KB Output is correct
5 Correct 51 ms 4032 KB Output is correct
6 Correct 10 ms 604 KB Output is correct
7 Correct 4061 ms 41016 KB Output is correct
8 Correct 4166 ms 41016 KB Output is correct
9 Correct 50 ms 5068 KB Output is correct
10 Correct 3978 ms 40888 KB Output is correct
11 Correct 3890 ms 41012 KB Output is correct
12 Correct 3955 ms 41012 KB Output is correct
13 Correct 3937 ms 40248 KB Output is correct
14 Correct 8427 ms 39812 KB Output is correct
15 Correct 8578 ms 39896 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 3695 ms 39800 KB Output is correct
18 Correct 7135 ms 39888 KB Output is correct
19 Correct 8568 ms 39860 KB Output is correct
20 Correct 8545 ms 40000 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 8633 ms 39924 KB Output is correct
24 Correct 3853 ms 39860 KB Output is correct
25 Correct 7098 ms 39884 KB Output is correct
26 Correct 3795 ms 20936 KB Output is correct
27 Correct 3748 ms 20952 KB Output is correct
28 Correct 51 ms 5312 KB Output is correct
29 Correct 3360 ms 20188 KB Output is correct
30 Correct 3149 ms 20184 KB Output is correct
31 Correct 1787 ms 18904 KB Output is correct
32 Correct 2542 ms 19404 KB Output is correct
33 Execution timed out 10024 ms 39896 KB Time limit exceeded
34 Halted 0 ms 0 KB -