Submission #48244101

---

Source Code Expand

// LUOGU_RID: 138522029
//Problem: 
#include<iostream>
#include<algorithm>
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define i32 INT_MAX
#define i64 LONG_LONG_MAX
#define pii std::pair<int, int>
#define pll std::pair<long long, long long>
#define pb push_back
#define fore(i,u,v) for(int i=head[u],v;i;i=e[i].nxt)
typedef long long ll;
const int N = 2e5 + 10;
ll read(){ll x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;}
void print(ll x){if(x<0)putchar('-'),x=-x;if(x>9)print(x/10);putchar(x%10+48);}
char gc(){char c=getchar();while(c==' '||c=='\n')c=getchar();return c;}
void pc(char Char){std::putchar(Char);}

int n;
ll k;
ll x[N], y[N], xs[N], ys[N];

bool check(ll len) {
    ll minx = INF, miny = INF, res;
    for(int i = 1; i <= n; i++) {
        // [ x[i], x[i] + len ]
        int Left = i - 1, Right = std::upper_bound(x + i + 1, x + n + 1, x[i] + len) - x;
        res = 0;
        if(Left >= 1) {
            res += x[i] * Left - xs[Left];
        }
        if(Right <= n) {
            res += xs[n] - xs[Right - 1] - (x[i] + len) * (n - Right + 1);
        }
        minx = std::min(minx, res);
        // [ x[i] - len, x[i] ]
        Left = std::lower_bound(x + 1, x + i + 1, x[i] - len) - x - 1, Right = i + 1;
        res = 0;
        if(Left >= 1) {
            res += (x[i] - len) * Left - xs[Left];
        }
        if(Right <= n) {
            res += xs[n] - xs[Right - 1] - x[i] * (n - Right + 1);
        }
        minx = std::min(minx, res);
    }
    for(int i = 1; i <= n; i++) {
        // [ y[i], y[i] + len ]
        int Left = i - 1, Right = std::upper_bound(y + i + 1, y + n + 1, y[i] + len) - y;
        res = 0;
        if(Left >= 1) {
            res += y[i] * Left - ys[Left];
        }
        if(Right <= n) {
            res += ys[n] - ys[Right - 1] - (y[i] + len) * (n - Right + 1);
        }
        miny = std::min(miny, res);
        // [ y[i] - len, y[i] ]
        Left = std::lower_bound(y + 1, y + i + 1, y[i] - len) - y - 1, Right = i + 1;
        res = 0;
        if(Left >= 1) {
            res += (y[i] - len) * Left - ys[Left];
        }
        if(Right <= n) {
            res += ys[n] - ys[Right - 1] - y[i] * (n - Right + 1);
        }
        miny = std::min(miny, res);
    }
    if(minx + miny > k) return 0;
    return 1;
}

int main() {
    std::cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        x[i] = read();
        y[i] = read();
    }
    std::sort(x + 1, x + n + 1);
    std::sort(y + 1, y + n + 1);
    for(int i = 1; i <= n; i++) {
        xs[i] = xs[i - 1] + x[i];
        ys[i] = ys[i - 1] + y[i];
    }
    ll l = 0, r = std::max(x[n] - x[1], y[n] - y[1]), ans = -1145141919810;
    while(l <= r) {
        ll mid = l + r >> 1;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    std::cout << ans << '\n';
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:88:20: warning: suggest parentheses around ‘+’ inside ‘>>’ [-Wparentheses]
   88 |         ll mid = l + r >> 1;
      |                  ~~^~~

Judge Result