Submission #389013

#	Time	Username	Problem	Language	Result	Execution time	Memory
389013		georgerapeanu	Road Construction (JOI21_road_construction)	C++11	38 / 100	10056 ms	24148 KiB

road_construction

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 25e4;

int n,k;

map<long long,int> to_norm;
pair<long long,long long> v[NMAX + 5];

class FenwickTree{
    vector<int> aib;
    int n;

public:

    FenwickTree(int n){
        this->n = n;
        this->aib = vector<int>(n + 1);
    }

    void update(int pos,int value){
        for(;pos <= n;pos += (-pos) & pos){
            aib[pos] += value;
        }
    }

    int query(int pos){
        int ans = 0;
        for(;pos;pos -= (-pos) & pos){
            ans += aib[pos];
        }
        return ans;
    }
    
    void reset(){
        for(auto &it:aib){
            it = 0;
        }
    }

}aib(0);

long long get_count(long long dist){
    aib.reset();
    int lst = 1;
    long long ans = 0;

    for(int i = 1;i <= n;i++){
        while(1LL * v[i].first - v[lst].first > dist){
            long long l = 1LL * v[lst].second - dist;
            long long r = 1LL * v[lst].second + dist;
            aib.update(to_norm.lower_bound(l)->second,-1);
            if(to_norm.lower_bound(r + 1) != to_norm.end()){
                aib.update(to_norm.lower_bound(r + 1)->second,1);
            }
            lst++;
        }

        ans += aib.query(to_norm[v[i].second]);
        long long l = 1LL * v[i].second - dist;
        long long r = 1LL * v[i].second + dist;

        aib.update(to_norm.lower_bound(l)->second,1);
        if(to_norm.lower_bound(r + 1) != to_norm.end()){
           aib.update(to_norm.lower_bound(r + 1)->second,-1);
        }
    }

    return ans;
}

vector<long long> get_distances(long long dist){
    vector<long long> ans;
    int lst = 1;
    set<pair<long long,long long> > s;
    for(int i = 1;i <= n;i++){
        while(1LL * v[i].first - v[lst].first > dist){
            s.erase({v[lst].second,v[lst].first});
            lst++;
        }
        for(set<pair<long long,long long> > :: iterator it = s.lower_bound({1LL * v[i].second - dist,-2e9 - 10});it != s.end() && it->first <= 1LL * v[i].second + dist;it++){
            ans.push_back(max(abs(v[i].first - it->second),abs(v[i].second - it->first)));
        }
        s.insert({v[i].second,v[i].first});
    }

    sort(ans.begin(),ans.end());
    return ans;
}

int main(){
    
    scanf("%d %d",&n,&k);

    aib = FenwickTree(n);

    for(int i = 1;i <= n;i++){
        int x,y;
        scanf("%d %d",&x,&y);
        v[i] = {x + y,x - y};
        to_norm[v[i].second] = 1;
    }

    sort(v + 1,v + 1 + n);

    int lst = 0;

    for(auto &it:to_norm){
        it.second = ++lst;
    }

    long long l = 0;
    long long r = 4e9 + 5;

    while(r - l > 1){
        long long mid = (1LL * l + 1LL * r) / 2;

        if(get_count(mid) < k){
            l = mid;
        }else{
            r = mid;
        }
    }

    vector<long long> ans = get_distances(l);

    while((int)ans.size() < k){
        ans.push_back(r);
    }

    for(auto it:ans){
        printf("%lld\n",it);
    }
    
    return 0;
}

Compilation message (stderr)

road_construction.cpp: In function 'int main()':
road_construction.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
road_construction.cpp:101:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |         scanf("%d %d",&x,&y);
      |         ~~~~~^~~~~~~~~~~~~~~

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