Language: C++

#include <iostream>
#include <cstdio>

#define debug 0

#define mk make_pair

using namespace std;
typedef long long lint;
typedef pair<lint, lint> pr;
const int maxn = 2e5+5, inf = 0x3f3f3f3f;

lint n, i, v[maxn], dp[maxn];

inline lint abs(lint x) {
    return (x < 0 ? -x : x);
}

// the pairs contain the smallest and biggest sums
pr bsearch2(lint st, lint dr) {

    lint p = 1 << 18, r = st - 1;
    lint r1, r2;
    while(p > 0) {
        if((r + p <= dr) && abs((dp[r + p] - dp[st - 1]) - (dp[dr] - dp[r + p])) >= abs((dp[r+1 + p] - dp[st - 1]) - (dp[dr] - dp[r+1 + p])))
        r += p;
        p >>= 1;
    }
    ++r;
    r1 = (dp[r] - dp[st - 1]);
    r2 = (dp[dr] - dp[r]);
    if(r1 > r2)
        swap(r1, r2);
    return mk(r1, r2);
}

pr bsearch3(lint st, lint dr) {

    lint p = 1 << 18, r = st - 1;
    lint r1, r2;
    while(p > 0) {
            if((r + p <= dr && (dr - (r + p) + 1 > 3)) && (  max(abs((dp[r + p] - dp[st - 1]) - bsearch2(r + p + 1, dr).first), abs((dp[r + p] - dp[st - 1]) - bsearch2(r + p + 1, dr).second)) >=
                                   max(abs((dp[r+1 + p] - dp[st - 1]) - bsearch2(r+1 + p + 1, dr).first), abs((dp[r+1 + p] - dp[st - 1]) - bsearch2(r+1 + p + 1, dr).second))
                                ))
            {
                pr bs2 = bsearch2(r+1 + p + 1, dr);
                r1 = min((dp[r+1 + p] - dp[st - 1]), bs2.first);
                r2 = max((dp[r+1 + p] - dp[st - 1]), bs2.second);
                r += p;
            }
        p >>= 1;
    }

    if(r == st - 1) {
            pr bs2 = bsearch2(r+1 + p + 1, dr);
            r1 = min((dp[r+1 + p] - dp[st - 1]), bs2.first);
            r2 = max((dp[r+1 + p] - dp[st - 1]), bs2.second);
    }

    if(r1 > r2)
        swap(r1, r2);
    return mk(r1, r2);
}

pr bsearch4(lint st, lint dr) {

    lint p = 1 << 18, r = st - 1;
    lint r1, r2;
    while(p > 0) {
            if((r + p <= dr && (dr - (r + p) + 1 > 4)) && (  max(abs((dp[r + p] - dp[st - 1]) - bsearch3(r + p + 1, dr).first), abs((dp[r + p] - dp[st - 1]) - bsearch3(r + p + 1, dr).second)) >=
                                   max(abs((dp[r+1 + p] - dp[st - 1]) - bsearch3(r+1 + p + 1, dr).first), abs((dp[r+1 + p] - dp[st - 1]) - bsearch3(r+1 + p + 1, dr).second))
                                ))
            {
                pr bs3 = bsearch3(r+1 + p + 1, dr);
                r1 = min((dp[r+1 + p] - dp[st - 1]), bs3.first);
                r2 = max((dp[r+1 + p] - dp[st - 1]), bs3.second);
                r += p;
            }
        p >>= 1;
    }
    if(r == st - 1) {
            pr bs3 = bsearch3(r+1 + p + 1, dr);
            r1 = min((dp[r+1 + p] - dp[st - 1]), bs3.first);
            r2 = max((dp[r+1 + p] - dp[st - 1]), bs3.second);
    }

    if(r1 > r2)
        swap(r1, r2);
    return mk(r1, r2);
}

int main()
{
    #if debug == 1
    freopen("f.in", "r", stdin);
    freopen("f.out", "w", stdout);
    #endif // debug

    cin >> n;
    for(i = 1; i <= n; i ++)
    {
        cin >> v[i];
        dp[i] = dp[i-1] + v[i];
    }
    pr x = bsearch4(1, n);
    cout << x.second - x.first;

    return 0;
}


Compiler output:
a.cc: In function 'pr bsearch2(lint, lint)':
a.cc:25:32: error: call of overloaded 'abs(lint)' is ambiguous
   25 |         if((r + p <= dr) && abs((dp[r + p] - dp[st - 1]) - (dp[dr] - dp[r + p])) >= abs((dp[r+1 + p] - dp[st - 1]) - (dp[dr] - dp[r+1 + p])))
      |                             ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/cstdlib:79,
                 from /usr/include/c++/14/ext/string_conversions.h:43,
                 from /usr/include/c++/14/bits/basic_string.h:4154,
                 from /usr/include/c++/14/string:54,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/stdlib.h:980:12: note: candidate: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
a.cc:15:13: note: candidate: 'lint abs(lint)'
   15 | inline lint abs(lint x) {
      |             ^~~
In file included from /usr/include/c++/14/cstdlib:81:
/usr/include/c++/14/bits/std_abs.h:137:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  137 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:85:3: note: candidate: 'constexpr __int128 std::abs(__int128)'
   85 |   abs(__GLIBCXX_TYPE_INT_N_0 __x) { return __x >= 0 ? __x : -__x; }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
a.cc:25:88: error: call of overloaded 'abs(lint)' is ambiguous
   25 |         if((r + p <= dr) && abs((dp[r + p] - dp[st - 1]) - (dp[dr] - dp[r + p])) >= abs((dp[r+1 + p] - dp[st - 1]) - (dp[dr] - dp[r+1 + p])))
      |                                                                                     ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/stdlib.h:980:12: note: candidate: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
a.cc:15:13: note: candidate: 'lint abs(lint)'
   15 | inline lint abs(lint x) {
      |             ^~~
/usr/include/c++/14/bits/std_abs.h:137:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  137 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:85:3: note: candidate: 'constexpr __int128 std::abs(__int128)'
   85 |   abs(__GLIBCXX_TYPE_INT_N_0 __x) { return __x >= 0 ? __x : -__x; }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
a.cc: In function 'pr bsearch3(lint, lint)':
a.cc:42:69: error: call of overloaded 'abs(lint)' is ambiguous
   42 |             if((r + p <= dr && (dr - (r + p) + 1 > 3)) && (  max(abs((dp[r + p] - dp[st - 1]) - bsearch2(r + p + 1, dr).first), abs((dp[r + p] - dp[st - 1]) - bsearch2(r + p + 1, dr).second)) >=
      |                                                                  ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/stdlib.h:980:12: note: candidate: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
a.cc:15:13: note: candidate: 'lint abs(lint)'
   15 | inline lint abs(lint x) {
      |             ^~~
/usr/include/c++/14/bits/std_abs.h:137:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  137 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:85:3: note: candidate: 'constexpr __int128 std::abs(__int128)'
   85 |   abs(__GLIBCXX_TYPE_INT_N_0 __x) { return __x >= 0 ? __x : -__x; }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
a.cc:42:132: error: call of overloaded 'abs(lint)' is ambiguous
   42 |             if((r + p <= dr && (dr - (r + p) + 1 > 3)) && (  max(abs((dp[r + p] - dp[st - 1]) - bsearch2(r + p + 1, dr).first), abs((dp[r + p] - dp[st - 1]) - bsearch2(r + p + 1, dr).second)) >=
      |                                                                                                                                 ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/stdlib.h:980:12: note: candidate: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
a.cc:15:13: note: candidate: 'lint abs(lint)'
   15 | inline lint abs(lint x) {
      |             ^~~
/usr/include/c++/14/bits/std_abs.h:137:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  137 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:85:3: note: candidate: 'constexpr __int128 std::abs(__int128)'
   85 |   abs(__GLIBCXX_TYPE_INT_N_0 __x) { return __x >= 0 ? __x : -__x; }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
a.cc:43:43: error: call of overloaded 'abs(lint)' is ambiguous
   43 |                                    max(abs((dp[r+1 + p] - dp[st - 1]) - bsearch2(r+1 + p + 1, dr).first), abs((dp[r+1 + p] - dp[st - 1]) - bsearch2(r+1 + p + 1, dr).second))
      |                                        ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/stdlib.h:980:12: note: candidate: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
a.cc:15:13: note: candidate: 'lint abs(lint)'
   15 | inline lint abs(lint x) {
      |             ^~~
/usr/include/c++/14/bits/std_abs.h:137:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  137 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:85:3: note: candidate: 'constexpr __int128 std::abs(__int128)'
   85 |   abs(__GLIBCXX_TYPE_INT_N_0 __x) { return __x >= 0 ? __x : -__x; }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:79:3: note: candidate: 'constexpr long double std::abs(long double)'
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:75:3: note: candidate: 'constexpr float std::abs(float)'
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:71:3: note: candidate: 'constexpr double std::abs(double)'
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:61:3: note: candidate: 'long long int std::abs(long long int)'
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:56:3: note: candidate: 'long int std::abs(long int)'
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
a.cc:43:110: error: call of overloaded 'abs(lint)' is ambiguous
   43 |                                    max(abs((dp[r+1 + p] - dp[st - 1]) - bsearch2(r+1 + p + 1, dr).first), abs((dp[r+1 + p] - dp[st - 1]) - bsearch2(r+1 + p + 1, dr).second))
      |                                                                                                           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/stdlib.h:980:12: note: candidate: 'int abs(int)'
  980 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
a.cc:15:13: note: candidate: 'lint abs(lint)'
   15 | inline lint abs(lint x) {
      |             ^~~
/usr/include/c++/14/bits/std_abs.h:137:3: note: candidate: 'constexpr __float128 std::abs(__float128)'
  137 |   abs(__float128 __x)
      |   ^~~
/usr/include/c++/14/bits/std_abs.h:85:3: note: candidate: 'constexpr