Submission #622788

#	Time	Username	Problem	Language	Result	Execution time	Memory
622788		dantoh000	Road Construction (JOI21_road_construction)	C++14	100 / 100	5887 ms	31144 KiB

road_construction

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii, int> iii;
int n, k;
int x[250005], y[250005];
vector<iii> P;
vector<int> ys;
int fw[250005];
void up(int x, int nv){
    while (x <= 250000){
        fw[x] += nv;
        x += x&-x;
    }
}
int qu(int x){
    int ret = 0;
    while (x){
        ret += fw[x];
        x -= x&-x;
    }
    return ret;
}
inline int lb(int y){
    return lower_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
}
inline int ub(int y){
    return upper_bound(ys.begin(), ys.end(), y) - ys.begin() + 1;
}


int test(int D){
    int c = 0;
    int ret = 0;
    for (auto it : P){
        int X = it.fi.fi, Y = it.fi.se;
        while (c < P.size() && P[c].fi.fi <= X + D){
            up(lb(P[c].fi.se), 1);
            c++;
        }
        up(lb(Y), -1);

        ret += qu(ub(Y + D) - 1) - qu(lb(Y-D) - 1);
        ///printf("%d %d %d\n",X,Y,id);
    }
    ///printf("%lld %lld\n",D,ret);
    return ret;
}
vector<int> solve(int D){
    int c = 0;
    vector<int> ret;
    set<ii> S;
    for (auto it : P){
        int X = it.fi.fi, Y = it.fi.se, id = it.se;
        while (c < P.size() && P[c].fi.fi <= X + D){
            S.insert({lb(P[c].fi.se), P[c].se});
            c++;
        }
        S.erase({lb(Y), id});
        for (auto it = S.lower_bound({lb(Y-D), -1}); it != S.end() && it != S.upper_bound({ub(Y+D),-1}); it++){
            int idx = it->se;
            ret.push_back(abs(x[idx] - x[id]) + abs(y[idx] - y[id]));
        }
        ///printf("%d %d %d\n",X,Y,id);
    }
    ///printf("%lld %lld\n",D,ret);
    return ret;

}



main(){
    scanf("%lld%lld",&n,&k);
    for (int i = 0; i < n; i++){
        scanf("%lld%lld",&x[i],&y[i]);
        int nx = x[i]+y[i];
        int ny = x[i]-y[i];
        ys.push_back(ny);
        P.push_back({{nx, ny}, i});
    }
    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    sort(P.begin(), P.end());

    int lo = 0, hi = 4000000000ll;
    while (lo < hi){
        int mid = (lo+hi)/2;
        if (test(mid) < k) lo = mid+1;
        else hi = mid;
    }
    vector<int> ans = solve(lo);
    sort(ans.begin(), ans.end());
    for (int i = 0; i < k; i++){
        printf("%lld\n",ans[i]);
    }


}

Compilation message (stderr)

road_construction.cpp: In function 'long long int test(long long int)':
road_construction.cpp:40:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         while (c < P.size() && P[c].fi.fi <= X + D){
      |                ~~^~~~~~~~~~
road_construction.cpp: In function 'std::vector<long long int> solve(long long int)':
road_construction.cpp:58:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         while (c < P.size() && P[c].fi.fi <= X + D){
      |                ~~^~~~~~~~~~
road_construction.cpp: At global scope:
road_construction.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   76 | main(){
      | ^~~~
road_construction.cpp: In function 'int main()':
road_construction.cpp:77:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |     scanf("%lld%lld",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
road_construction.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf("%lld%lld",&x[i],&y[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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