Submission #63281378

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;

#define INF 1234567890
#define ll long long

int N;
ll X;
ll U[202020], D[202020];

bool f(ll H)
{
    ll UL = -(ll)1e18, UR = (ll)1e18;
    for(int i=1; i<=N; i++)
    {
        // U[i] + D[i] = H가 되어야 한다.
        ll sub = U[i] + D[i] - H;

        ll minU = max(0LL, sub - D[i]);

        ll ul = max(1LL, U[i] - sub);
        ll ur = U[i] - minU;

        ll dl = H - ur;
        ll dr = H - ul;

        if (ul > ur) return false;


        UL -= X;
        UR += X;
        UL = max(UL, ul);
        UR = min(UR, ur);
        if (i >= 2)
        {
            ll DL = H - UR;
            ll DR = H - UL;

            DL -= X;
            DR += X;
            DL = max(DL, dl);
            DR = min(DR, dr);

            UL = max(UL, H-DR);
            UR = min(UR, H-DL);
        }
        
        if (UL > UR) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> N >> X;
    ll ub = (ll)1e18, sum = 0;
    for(int i=1; i<=N; i++)
    {
        cin >> U[i] >> D[i];
        ub = min(ub, U[i] + D[i]);
        sum += U[i] + D[i];
    }
    // H \in [2, ub]
    ll lo = 2, hi = ub+1;
    for(int i=0; i<40; i++)
    {
        ll mid = lo+hi>>1;
        if (f(mid)) lo = mid;
        else hi = mid;
    }
    cout << sum - lo*N << "\n";
    return 0;
}

Submission Info

Compile Error

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

Judge Result