oj.uz

Submission #1079959

# Submission time Handle Problem Language Result Execution time Memory
1079959 2024-08-29T04:59:53 Z nathan4690 Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 52668 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<long long> bit;
    FenwickTree(){}
    FenwickTree(int n): n(n), bit(n+1, 0LL){}
    void update(int idx, long long v){
        if(idx <= 0) return;
        for(;idx<=n;idx+=(idx&-idx)) bit[idx]+=v;
    }
    long long getSum(int idx){
        if(idx <= 0) return 0;
        long long 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 58 ms 7632 KB Output is correct
2 Correct 62 ms 7212 KB Output is correct
3 Correct 50 ms 7364 KB Output is correct
4 Correct 51 ms 7428 KB Output is correct
5 Correct 54 ms 6084 KB Output is correct
6 Correct 10 ms 2736 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4030 ms 50024 KB Output is correct
2 Correct 4167 ms 50208 KB Output is correct
3 Correct 43 ms 7108 KB Output is correct
4 Correct 4056 ms 50076 KB Output is correct
5 Correct 3943 ms 49836 KB Output is correct
6 Correct 3974 ms 50264 KB Output is correct
7 Correct 4009 ms 49264 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8692 ms 51284 KB Output is correct
2 Correct 8690 ms 52400 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 3799 ms 48572 KB Output is correct
5 Correct 6981 ms 52668 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8692 ms 51284 KB Output is correct
2 Correct 8690 ms 52400 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 3799 ms 48572 KB Output is correct
5 Correct 6981 ms 52668 KB Output is correct
6 Correct 8791 ms 52396 KB Output is correct
7 Correct 8789 ms 51140 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 8812 ms 51292 KB Output is correct
11 Correct 3894 ms 48952 KB Output is correct
12 Correct 6917 ms 51544 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7632 KB Output is correct
2 Correct 62 ms 7212 KB Output is correct
3 Correct 50 ms 7364 KB Output is correct
4 Correct 51 ms 7428 KB Output is correct
5 Correct 54 ms 6084 KB Output is correct
6 Correct 10 ms 2736 KB Output is correct
7 Correct 3625 ms 29412 KB Output is correct
8 Correct 3653 ms 28144 KB Output is correct
9 Correct 50 ms 7368 KB Output is correct
10 Correct 3203 ms 25212 KB Output is correct
11 Correct 3035 ms 25208 KB Output is correct
12 Correct 1678 ms 25168 KB Output is correct
13 Correct 2463 ms 25724 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 7632 KB Output is correct
2 Correct 62 ms 7212 KB Output is correct
3 Correct 50 ms 7364 KB Output is correct
4 Correct 51 ms 7428 KB Output is correct
5 Correct 54 ms 6084 KB Output is correct
6 Correct 10 ms 2736 KB Output is correct
7 Correct 4030 ms 50024 KB Output is correct
8 Correct 4167 ms 50208 KB Output is correct
9 Correct 43 ms 7108 KB Output is correct
10 Correct 4056 ms 50076 KB Output is correct
11 Correct 3943 ms 49836 KB Output is correct
12 Correct 3974 ms 50264 KB Output is correct
13 Correct 4009 ms 49264 KB Output is correct
14 Correct 8692 ms 51284 KB Output is correct
15 Correct 8690 ms 52400 KB Output is correct
16 Correct 1 ms 2648 KB Output is correct
17 Correct 3799 ms 48572 KB Output is correct
18 Correct 6981 ms 52668 KB Output is correct
19 Correct 8791 ms 52396 KB Output is correct
20 Correct 8789 ms 51140 KB Output is correct
21 Correct 1 ms 2392 KB Output is correct
22 Correct 1 ms 2396 KB Output is correct
23 Correct 8812 ms 51292 KB Output is correct
24 Correct 3894 ms 48952 KB Output is correct
25 Correct 6917 ms 51544 KB Output is correct
26 Correct 3625 ms 29412 KB Output is correct
27 Correct 3653 ms 28144 KB Output is correct
28 Correct 50 ms 7368 KB Output is correct
29 Correct 3203 ms 25212 KB Output is correct
30 Correct 3035 ms 25208 KB Output is correct
31 Correct 1678 ms 25168 KB Output is correct
32 Correct 2463 ms 25724 KB Output is correct
33 Execution timed out 10047 ms 52188 KB Time limit exceeded
34 Halted 0 ms 0 KB -