Submission #1007698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007698		Unforgettablepl	Road Construction (JOI21_road_construction)	C++17	65 / 100	10037 ms	415436 KiB

road_construction

#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;
    #pragma GCC unroll 40
    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 (stderr)

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:105: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]
  105 |         if(i<edgewt.size())cout<<edgewt[i]<<'\n';
      |            ~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 20 / 20
• Subtask 5: 27 / 27
• Subtask 6: 0 / 35