# CFR 429 D. Tricky Function ( Divide and Conquer, Closest Pair )

Problem - D - Codeforces

The first line of input contains a single integer n (2 ≤ n ≤ 100000). Next line contains n integers a[1], a[2], ..., a[n] ( - 1e4 ≤ a[i] ≤ 1e4).

O( N lg N )

http://codeforces.com/contest/429/submission/6593023

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

typedef long long ll;

const int MAXN = ( int ) 1e5;

int N;
int A[ MAXN ];
ll pfx[ MAXN + 1 ];

ll sqr( ll x ){ return x * x; }

ll rec_solve( vector< pair< ll, ll > > &pnt, int lb, int rb ){
if( lb + 1 == rb ) return 1LL << 50;
int mid = lb + rb >> 1;
ll mx = pnt[ mid ].first;
ll res = min( rec_solve( pnt, lb, mid ), rec_solve( pnt, mid, rb ) );
vector< pair< ll, ll > > interesting;
for( int i = lb; i < rb; ++i ){
if( sqr( pnt[ i ].first - mx ) < res ){
interesting.emplace_back( pnt[ i ] );
}
}
sort( interesting.begin(), interesting.end(),
[ & ]( pair< ll, ll > i, pair< ll, ll > j ){ return i.second < j.second; } );
vector< pair< ll, ll > > t;
for( int i = 0; i < interesting.size(); ++i ){
if( sqr( interesting[ i ].first - mx ) >= res ) continue;
for( int j = t.size() - 1; j >= 0; --j ){
ll dx = interesting[ i ].first - t[ j ].first;
ll dy = interesting[ i ].second - t[ j ].second;
if( sqr( dy ) >= res ) break;
res = min( res, sqr( dx ) + sqr( dy ) );
}
t.emplace_back( interesting[ i ] );
}
return res;
}

signed main(){
ios::sync_with_stdio( 0 );
cin >> N;
for( int i = 0; i < N; ++i ){
cin >> A[ i ];
}
for( int i = 0; i < N; ++i ){
pfx[ i + 1 ] = pfx[ i ] + A[ i ];
}
vector< pair< ll, ll > > pnt( N );
for( int i = 1; i <= N; ++i ){
pnt[ i - 1 ] = make_pair( i, pfx[ i ] );
}
sort( pnt.begin(), pnt.end() );
cout << rec_solve( pnt, 0, N ) << endl;
return 0;
}