提出 #47937860

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

using _loop_int = int;
#define REP(i,n) for(_loop_int i=0; i<(_loop_int)(n); i++)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a); i<(_loop_int)(b); i++)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1; i>=(_loop_int)(a); i--)

#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))
#define ALL(v) (v).begin(),(v).end()

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl

const ll MOD = 1000000007ll;

int n;
ll k;
pii pts[252521];

int main(){
    #if 1
    scanf("%d%lld",&n,&k);
    REP(i,n){int x,y;scanf("%d%d",&x,&y);pts[i]=pii(x,y);}
    #else
    srand(830252);
    n = 200000;
    k = 4'000'000'000'000ll;
    REP(i,n){
        int x,y;
        x = rand() % 1'000'000'000;
        y = rand() % 1'000'000'000;
        pts[i] = pii(x,y);
    }
    #endif

    vl xs(n), ys(n);
    REP(i,n)xs[i]=pts[i].first,ys[i]=pts[i].second;
    sort(ALL(xs));sort(ALL(ys));
    vl yys(n);
    yys[0] = 0ll;  // 1*(y-ys[0]) + 0
    FOR(i,1,n){
        yys[i] = yys[i-1] + 1ll*(ys[i]-ys[i-1])*i;
    }
    vl yys2(n);
    yys2[n-1] = 0ll;
    FORR(i,0,n-1){
        yys2[i] = yys2[i+1] + 1ll*(ys[i+1]-ys[i])*(n-1-i);
    }
    vl xxs(n);
    xxs[0] = 0ll;  // 1*(x-xs[0]) + 0
    FOR(i,1,n){
        xxs[i] = xxs[i-1] + 1ll*(xs[i]-xs[i-1])*i;
    }
    vl xxs2(n);
    xxs2[n-1] = 0ll;
    FORR(i,0,n-1){
        xxs2[i] = xxs2[i+1] + 1ll*(xs[i+1]-xs[i])*(n-1-i);
    }

    auto fx = [&](){
        ll ok = 1'000'000'005, ng=-1;
        while(abs(ok-ng)>1) {
            ll len = (ok+ng)/2;

            ll xmin = k+1ll;
            ll ymin = k+1ll;
            {
                const vl& ss = xs;
                const vl& ssa = xxs;
                const vl& ssb = xxs2;
                {
                    int top = 0;
                    REP(bot,n){
                        while(top+1<n && ss[top+1]-ss[bot] <= len) top++;
                        ll v = ssa[bot];
                        if (top+1<n) v += ssb[top+1] + 1ll*(ss[top+1]-ss[bot]-len)*(n-1-top);
                        CHMIN(xmin,v);
                    }
                }
                {
                    int bot = n-1;
                    FORR(top,0,n){
                        while(bot-1>=0 && ss[top]-ss[bot-1] <= len) bot--;
                        ll v = ssb[top];
                        if (bot-1>=0) v += ssa[bot-1] + 1ll*(ss[top]-len-ss[bot-1])*bot;
                        CHMIN(xmin,v);
                    }
                }
            }
            {
                const vl& ss = ys;
                const vl& ssa = yys;
                const vl& ssb = yys2;
                {
                    int top = 0;
                    REP(bot,n){
                        while(top+1<n && ss[top+1]-ss[bot] <= len) top++;
                        ll v = ssa[bot];
                        if (top+1<n) v += ssb[top+1] + 1ll*(ss[top+1]-ss[bot]-len)*(n-1-top);
                        CHMIN(ymin,v);
                    }
                }
                {
                    int bot = n-1;
                    FORR(top,0,n){
                        while(bot-1>=0 && ss[top]-ss[bot-1] <= len) bot--;
                        ll v = ssb[top];
                        if (bot-1>=0) v += ssa[bot-1] + 1ll*(ss[top]-len-ss[bot-1])*bot;
                        CHMIN(ymin,v);
                    }
                }
            }
            (xmin+ymin<=k ? ok : ng) = len;
        }
        return ok;
    };
    ll ans = fx();
    printf("%lld\n",ans);
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:31:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |     scanf("%d%lld",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:32:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   32 |     REP(i,n){int x,y;scanf("%d%d",&x,&y);pts[i]=pii(x,y);}
      |                      ~~~~~^~~~~~~~~~~~~~

ジャッジ結果