oj.uz

Submission #1007588

# Submission time Handle Problem Language Result Execution time Memory
1007588 2024-06-25T08:17:16 Z Unforgettablepl Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 413232 KB 
#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;


#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

#define int long long
typedef tree<pair<int,int>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> orderedset;

orderedset seg[1000000];
vector<pair<int,int>> points;
vector<pair<int,int>> edges;
int n;

void build(int x=1,int L=1,int R=n){
    if(L==R){
        seg[x].insert({points[L].second,L});
        return;
    }
    int mid = (L+R)/2;
    build(2*x,L,mid);
    build(2*x+1,mid+1,R);
    for(auto i:seg[2*x])seg[x].insert(i);
    for(auto i:seg[2*x+1])seg[x].insert(i);
}

int get(int qL,int qR,int qUpper,int qLower,int x=1,int L=1,int R=n){
    if(qR<L or R<qL)return 0;
    if(qL<=L and R<=qR){
        return seg[x].order_of_key({qUpper+1,0})-seg[x].order_of_key({qLower,0});
    }
    int mid = (L+R)/2;
    return get(qL,qR,qUpper,qLower,2*x,L,mid)+get(qL,qR,qUpper,qLower,2*x+1,mid+1,R);
}

int base;

void debug(int x){
    for(int i=0;i<seg[x].size();i++)cerr<<seg[x].find_by_order(i)->first<<' ';
}

void rec(int qL,int qR,int qUpper,int qLower,int x=1,int L=1,int R=n){
    if(qR<L or R<qL)return;
    if(qL<=L and R<=qR){
        auto lo = seg[x].order_of_key({qLower,0});
        auto hi = seg[x].order_of_key({qUpper+1,0});
        while(lo!=hi){
            edges.emplace_back(min(base,(int)seg[x].find_by_order(lo)->second),max(base,(int)seg[x].find_by_order(lo)->second));
            lo++;
        }
        return;
    }
    int mid = (L+R)/2;
    rec(qL,qR,qUpper,qLower,2*x,L,mid);
    rec(qL,qR,qUpper,qLower,2*x+1,mid+1,R);
}


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        int x,y;
        cin >> x >> y;swap(x,y);
        points.emplace_back(x-y,x+y);
    }
    sort(points.begin(),points.end());
    points.insert(points.begin(),{0,0});
    build();
    auto calc = [&](int limit){
        int curr = 0;
        for(int i=1;i<=n;i++){
            int qL = lower_bound(points.begin()+1,points.end(),make_pair(points[i].first-limit,0ll))-points.begin();
            int qR = lower_bound(points.begin()+1,points.end(),make_pair(points[i].first+limit,0ll))-points.begin()-1;
            curr+=get(qL,qR,points[i].second+limit,points[i].second-limit);
        }
        curr-=n;
        return curr<2*k;
    };
    vector<int> edgewt;
    auto recover = [&](int limit){
        for(int i=1;i<=n;i++){
            int qL = lower_bound(points.begin(),points.end(),make_pair(points[i].first-limit,0ll))-points.begin();
            int qR = lower_bound(points.begin(),points.end(),make_pair(points[i].first+limit,0ll))-points.begin()-1;
            base = i;
            rec(qL,qR,points[i].second+limit,points[i].second-limit);
        }
        sort(edges.begin(),edges.end());
        edges.erase(unique(edges.begin(),edges.end()),edges.end());
        for(auto[a,b]:edges){
            if(a==b)continue;
            edgewt.emplace_back(max(abs(points[a].first-points[b].first),abs(points[a].second-points[b].second)));
        }
        sort(edgewt.begin(),edgewt.end());
    };
    int ans = 0;
    for(int jump=2147483648ll;jump;jump/=2)if(calc(ans+jump))ans+=jump;
    recover(ans);
    for(int i=0;i<k;i++){
        if(i<edgewt.size())cout<<edgewt[i]<<'\n';
        else cout<<ans+1<<'\n';
    }
}

Compilation message

road_construction.cpp: In function 'void debug(long long int)':
road_construction.cpp:41:18: warning: comparison of integer expressions of different signedness: 'long long int' and '__gnu_pbds::detail::bin_search_tree_set<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::less<void>, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::less<void>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=0;i<seg[x].size();i++)cerr<<seg[x].find_by_order(i)->first<<' ';
      |                 ~^~~~~~~~~~~~~~
road_construction.cpp: In function 'int32_t main()':
road_construction.cpp:104:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         if(i<edgewt.size())cout<<edgewt[i]<<'\n';
      |            ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 109488 KB Output is correct
2 Correct 150 ms 109496 KB Output is correct
3 Correct 147 ms 109228 KB Output is correct
4 Correct 142 ms 109228 KB Output is correct
5 Correct 129 ms 108180 KB Output is correct
6 Correct 52 ms 95128 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4769 ms 413232 KB Output is correct
2 Correct 4790 ms 412976 KB Output is correct
3 Correct 124 ms 109484 KB Output is correct
4 Correct 4740 ms 412612 KB Output is correct
5 Correct 4853 ms 413228 KB Output is correct
6 Correct 4898 ms 412968 KB Output is correct
7 Correct 4543 ms 412516 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7679 ms 401276 KB Output is correct
2 Correct 7922 ms 403108 KB Output is correct
3 Correct 48 ms 94268 KB Output is correct
4 Correct 4727 ms 402100 KB Output is correct
5 Correct 6465 ms 402416 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7679 ms 401276 KB Output is correct
2 Correct 7922 ms 403108 KB Output is correct
3 Correct 48 ms 94268 KB Output is correct
4 Correct 4727 ms 402100 KB Output is correct
5 Correct 6465 ms 402416 KB Output is correct
6 Correct 7888 ms 401652 KB Output is correct
7 Correct 7910 ms 402348 KB Output is correct
8 Correct 49 ms 94284 KB Output is correct
9 Correct 50 ms 94292 KB Output is correct
10 Correct 7691 ms 401648 KB Output is correct
11 Correct 4762 ms 402680 KB Output is correct
12 Correct 6251 ms 402076 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 109488 KB Output is correct
2 Correct 150 ms 109496 KB Output is correct
3 Correct 147 ms 109228 KB Output is correct
4 Correct 142 ms 109228 KB Output is correct
5 Correct 129 ms 108180 KB Output is correct
6 Correct 52 ms 95128 KB Output is correct
7 Correct 4289 ms 224812 KB Output is correct
8 Correct 4169 ms 223276 KB Output is correct
9 Correct 144 ms 109228 KB Output is correct
10 Correct 3245 ms 224768 KB Output is correct
11 Correct 3079 ms 223740 KB Output is correct
12 Correct 2526 ms 227180 KB Output is correct
13 Correct 2161 ms 225080 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 109488 KB Output is correct
2 Correct 150 ms 109496 KB Output is correct
3 Correct 147 ms 109228 KB Output is correct
4 Correct 142 ms 109228 KB Output is correct
5 Correct 129 ms 108180 KB Output is correct
6 Correct 52 ms 95128 KB Output is correct
7 Correct 4769 ms 413232 KB Output is correct
8 Correct 4790 ms 412976 KB Output is correct
9 Correct 124 ms 109484 KB Output is correct
10 Correct 4740 ms 412612 KB Output is correct
11 Correct 4853 ms 413228 KB Output is correct
12 Correct 4898 ms 412968 KB Output is correct
13 Correct 4543 ms 412516 KB Output is correct
14 Correct 7679 ms 401276 KB Output is correct
15 Correct 7922 ms 403108 KB Output is correct
16 Correct 48 ms 94268 KB Output is correct
17 Correct 4727 ms 402100 KB Output is correct
18 Correct 6465 ms 402416 KB Output is correct
19 Correct 7888 ms 401652 KB Output is correct
20 Correct 7910 ms 402348 KB Output is correct
21 Correct 49 ms 94284 KB Output is correct
22 Correct 50 ms 94292 KB Output is correct
23 Correct 7691 ms 401648 KB Output is correct
24 Correct 4762 ms 402680 KB Output is correct
25 Correct 6251 ms 402076 KB Output is correct
26 Correct 4289 ms 224812 KB Output is correct
27 Correct 4169 ms 223276 KB Output is correct
28 Correct 144 ms 109228 KB Output is correct
29 Correct 3245 ms 224768 KB Output is correct
30 Correct 3079 ms 223740 KB Output is correct
31 Correct 2526 ms 227180 KB Output is correct
32 Correct 2161 ms 225080 KB Output is correct
33 Execution timed out 10050 ms 394940 KB Time limit exceeded
34 Halted 0 ms 0 KB -