oj.uz

Submission #1007698

# Submission time Handle Problem Language Result Execution time Memory
1007698 2024-06-25T10:33:46 Z Unforgettablepl Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 415436 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;
    #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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 109528 KB Output is correct
2 Correct 155 ms 109488 KB Output is correct
3 Correct 147 ms 109492 KB Output is correct
4 Correct 143 ms 109316 KB Output is correct
5 Correct 142 ms 108464 KB Output is correct
6 Correct 55 ms 94960 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4690 ms 414592 KB Output is correct
2 Correct 4589 ms 415436 KB Output is correct
3 Correct 124 ms 109204 KB Output is correct
4 Correct 4816 ms 415016 KB Output is correct
5 Correct 4865 ms 414756 KB Output is correct
6 Correct 4617 ms 414824 KB Output is correct
7 Correct 4441 ms 414744 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8225 ms 403952 KB Output is correct
2 Correct 7839 ms 404496 KB Output is correct
3 Correct 50 ms 94292 KB Output is correct
4 Correct 4930 ms 402972 KB Output is correct
5 Correct 6568 ms 404584 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8225 ms 403952 KB Output is correct
2 Correct 7839 ms 404496 KB Output is correct
3 Correct 50 ms 94292 KB Output is correct
4 Correct 4930 ms 402972 KB Output is correct
5 Correct 6568 ms 404584 KB Output is correct
6 Correct 8012 ms 405228 KB Output is correct
7 Correct 8129 ms 405232 KB Output is correct
8 Correct 48 ms 94228 KB Output is correct
9 Correct 49 ms 94284 KB Output is correct
10 Correct 7891 ms 405940 KB Output is correct
11 Correct 4746 ms 403624 KB Output is correct
12 Correct 6175 ms 404596 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 109528 KB Output is correct
2 Correct 155 ms 109488 KB Output is correct
3 Correct 147 ms 109492 KB Output is correct
4 Correct 143 ms 109316 KB Output is correct
5 Correct 142 ms 108464 KB Output is correct
6 Correct 55 ms 94960 KB Output is correct
7 Correct 4048 ms 225776 KB Output is correct
8 Correct 3950 ms 225496 KB Output is correct
9 Correct 143 ms 109228 KB Output is correct
10 Correct 2761 ms 225844 KB Output is correct
11 Correct 2531 ms 225012 KB Output is correct
12 Correct 2156 ms 227624 KB Output is correct
13 Correct 2191 ms 224824 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 109528 KB Output is correct
2 Correct 155 ms 109488 KB Output is correct
3 Correct 147 ms 109492 KB Output is correct
4 Correct 143 ms 109316 KB Output is correct
5 Correct 142 ms 108464 KB Output is correct
6 Correct 55 ms 94960 KB Output is correct
7 Correct 4690 ms 414592 KB Output is correct
8 Correct 4589 ms 415436 KB Output is correct
9 Correct 124 ms 109204 KB Output is correct
10 Correct 4816 ms 415016 KB Output is correct
11 Correct 4865 ms 414756 KB Output is correct
12 Correct 4617 ms 414824 KB Output is correct
13 Correct 4441 ms 414744 KB Output is correct
14 Correct 8225 ms 403952 KB Output is correct
15 Correct 7839 ms 404496 KB Output is correct
16 Correct 50 ms 94292 KB Output is correct
17 Correct 4930 ms 402972 KB Output is correct
18 Correct 6568 ms 404584 KB Output is correct
19 Correct 8012 ms 405228 KB Output is correct
20 Correct 8129 ms 405232 KB Output is correct
21 Correct 48 ms 94228 KB Output is correct
22 Correct 49 ms 94284 KB Output is correct
23 Correct 7891 ms 405940 KB Output is correct
24 Correct 4746 ms 403624 KB Output is correct
25 Correct 6175 ms 404596 KB Output is correct
26 Correct 4048 ms 225776 KB Output is correct
27 Correct 3950 ms 225496 KB Output is correct
28 Correct 143 ms 109228 KB Output is correct
29 Correct 2761 ms 225844 KB Output is correct
30 Correct 2531 ms 225012 KB Output is correct
31 Correct 2156 ms 227624 KB Output is correct
32 Correct 2191 ms 224824 KB Output is correct
33 Execution timed out 10037 ms 397636 KB Time limit exceeded
34 Halted 0 ms 0 KB -