Submission #1111322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111322		onlk97	Road Construction (JOI21_road_construction)	C++14	100 / 100	3973 ms	28964 KiB

road_construction

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,k;
    cin>>n>>k;
    pii a[n+1];
    for (int i=1; i<=n; i++){
        int u,v; cin>>u>>v;
        a[i]={u-v,u+v};
    }
    sort(a+1,a+n+1);
    int l=1,r=4e9;
    tree <pii,null_type,less <pii>,rb_tree_tag,tree_order_statistics_node_update> s;
    while (l<r){
        int mid=(l+r)/2;
        s.clear();
        int cnt=0,lst=1;
        for (int i=1; i<=n; i++){
            while (lst<i&&a[lst].x<a[i].x-mid){
                s.erase({a[lst].y,lst});
                lst++;
            }
            cnt+=s.order_of_key({a[i].y+mid+1,0})-s.order_of_key({a[i].y-mid,0});
            s.insert({a[i].y,i});
        }
        if (cnt>=k) r=mid;
        else l=mid+1;
    }
    l--;
    vector <int> vec;
    s.clear();
    int lst=1;
    for (int i=1; i<=n; i++){
        while (lst<i&&a[lst].x<a[i].x-l){
            s.erase({a[lst].y,lst});
            lst++;
        }
        int idx=s.order_of_key({a[i].y-l,0});
        while (idx<s.size()){
            pii tp=*s.find_by_order(idx);
            if (tp.x>a[i].y+l) break;
            vec.pb(max(a[i].x-a[tp.y].x,abs(a[i].y-tp.x)));
            idx++;
        }
        s.insert({a[i].y,i});
    }
    sort(vec.begin(),vec.end());
    while (vec.size()<k) vec.pb(l+1);
    for (int i:vec) cout<<i<<'\n';
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:48:19: 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<std::pair<long long int, long long int> >, __gnu_pbds::detail::tree_traits<std::pair<long long int, long long int>, __gnu_pbds::null_type, std::less<std::pair<long long int, long long int> >, __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]
   48 |         while (idx<s.size()){
      |                ~~~^~~~~~~~~
road_construction.cpp:57:22: 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]
   57 |     while (vec.size()<k) vec.pb(l+1);
      |            ~~~~~~~~~~^~

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