oj.uz

Submission #1007700

# Submission time Handle Problem Language Result Execution time Memory
1007700 2024-06-25T10:48:21 Z Unforgettablepl Road Construction (JOI21_road_construction) C++17
65 / 100
 10000 ms 413672 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 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;
        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,(int)-1e15))-points.begin();
            int qR = lower_bound(points.begin()+1,points.end(),make_pair(points[i].first+limit,(int)-1e15))-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,(int)-1e15))-points.begin();
            int qR = lower_bound(points.begin(),points.end(),make_pair(points[i].first+limit,(int)-1e15))-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 'int32_t main()':
road_construction.cpp:101: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]
  101 |         if(i<edgewt.size())cout<<edgewt[i]<<'\n';
      |            ~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 109752 KB Output is correct
2 Correct 143 ms 109492 KB Output is correct
3 Correct 126 ms 109488 KB Output is correct
4 Correct 132 ms 109232 KB Output is correct
5 Correct 141 ms 108208 KB Output is correct
6 Correct 51 ms 95084 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4670 ms 412712 KB Output is correct
2 Correct 4923 ms 412968 KB Output is correct
3 Correct 122 ms 109232 KB Output is correct
4 Correct 4963 ms 413672 KB Output is correct
5 Correct 5117 ms 413048 KB Output is correct
6 Correct 5177 ms 412584 KB Output is correct
7 Correct 4771 ms 411988 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7826 ms 401312 KB Output is correct
2 Correct 7689 ms 402356 KB Output is correct
3 Correct 46 ms 94292 KB Output is correct
4 Correct 5076 ms 402704 KB Output is correct
5 Correct 6424 ms 401740 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7826 ms 401312 KB Output is correct
2 Correct 7689 ms 402356 KB Output is correct
3 Correct 46 ms 94292 KB Output is correct
4 Correct 5076 ms 402704 KB Output is correct
5 Correct 6424 ms 401740 KB Output is correct
6 Correct 7829 ms 401652 KB Output is correct
7 Correct 7607 ms 401592 KB Output is correct
8 Correct 70 ms 94288 KB Output is correct
9 Correct 50 ms 94288 KB Output is correct
10 Correct 7617 ms 402004 KB Output is correct
11 Correct 5197 ms 401076 KB Output is correct
12 Correct 6389 ms 403168 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 109752 KB Output is correct
2 Correct 143 ms 109492 KB Output is correct
3 Correct 126 ms 109488 KB Output is correct
4 Correct 132 ms 109232 KB Output is correct
5 Correct 141 ms 108208 KB Output is correct
6 Correct 51 ms 95084 KB Output is correct
7 Correct 4297 ms 224812 KB Output is correct
8 Correct 4126 ms 223532 KB Output is correct
9 Correct 148 ms 109312 KB Output is correct
10 Correct 2949 ms 224500 KB Output is correct
11 Correct 2508 ms 224304 KB Output is correct
12 Correct 2066 ms 226172 KB Output is correct
13 Correct 2074 ms 223796 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 109752 KB Output is correct
2 Correct 143 ms 109492 KB Output is correct
3 Correct 126 ms 109488 KB Output is correct
4 Correct 132 ms 109232 KB Output is correct
5 Correct 141 ms 108208 KB Output is correct
6 Correct 51 ms 95084 KB Output is correct
7 Correct 4670 ms 412712 KB Output is correct
8 Correct 4923 ms 412968 KB Output is correct
9 Correct 122 ms 109232 KB Output is correct
10 Correct 4963 ms 413672 KB Output is correct
11 Correct 5117 ms 413048 KB Output is correct
12 Correct 5177 ms 412584 KB Output is correct
13 Correct 4771 ms 411988 KB Output is correct
14 Correct 7826 ms 401312 KB Output is correct
15 Correct 7689 ms 402356 KB Output is correct
16 Correct 46 ms 94292 KB Output is correct
17 Correct 5076 ms 402704 KB Output is correct
18 Correct 6424 ms 401740 KB Output is correct
19 Correct 7829 ms 401652 KB Output is correct
20 Correct 7607 ms 401592 KB Output is correct
21 Correct 70 ms 94288 KB Output is correct
22 Correct 50 ms 94288 KB Output is correct
23 Correct 7617 ms 402004 KB Output is correct
24 Correct 5197 ms 401076 KB Output is correct
25 Correct 6389 ms 403168 KB Output is correct
26 Correct 4297 ms 224812 KB Output is correct
27 Correct 4126 ms 223532 KB Output is correct
28 Correct 148 ms 109312 KB Output is correct
29 Correct 2949 ms 224500 KB Output is correct
30 Correct 2508 ms 224304 KB Output is correct
31 Correct 2066 ms 226172 KB Output is correct
32 Correct 2074 ms 223796 KB Output is correct
33 Execution timed out 10065 ms 394936 KB Time limit exceeded
34 Halted 0 ms 0 KB -