Submission #16707309

---

Source Code Expand

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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define test() int t;cin>>t;for(int test=1;test<=t;test++)
#define pb push_back
#define nl cout<<"\n"
#define F first
#define S second
#define all(x) x.begin(),x.end()

template<class C> void min_self( C &a, C b ){ a = min(a,b); }
template<class C> void max_self( C &a, C b ){ a = max(a,b); }

const ll MOD = 1000000007;
ll mod( ll n, ll m=MOD ){ n%=m,n+=m,n%=m;return n; }

const int MAXN = 1e5+5;
const int LOGN = 21;
const ll INF = 1e14;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

template<class T1, class T2> void add( T1 &x, T2 y, ll m = MOD )
{
    x += y;
    if( x >= m )
        x -= m;
}

template<class T1, class T2> void sub( T1 &x, T2 y, ll m = MOD )
{
    x -= y;
    if( x < 0 )
        x += m;
}

struct Point
{
    int x,y;
    bool operator <( Point& other )
    {
        return x < other.x;
    }
};

vector<int>max_seg, min_seg;
int N;

void update( vector<int>&t, int type, int pos, int val )
{
    pos += N;
    t[pos] = val;
    for(; pos > 1 ; pos >>= 1 )
    {
        if( type == 0 )
            t[pos/2] = max( t[pos], t[pos^1] );
        else
            t[pos/2] = min( t[pos], t[pos^1] );
    }
}

int query( vector<int>&t, int type, int l, int r )
{
    l += N;
    r += N+1;
    int ans = ( type == 0 ? -MOD : MOD );
    for(; l < r ; l >>= 1, r >>= 1 )
    {
        if( l&1 )
            ans = ( type == 0 ? max(ans, t[l++]) : min(ans, t[l++]) );
        if( r&1 )
            ans = ( type == 0 ? max(ans, t[--r]) : min(ans, t[--r]) );
    }
    return ans;
}

int main() 
{
    #ifdef gupta_samarth
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    fastio();

    int n;
    cin>>n;
    vector<Point>v(n);
    vector<int>ys;
    for(int i=0;i<n;i++)
    {
        cin>>v[i].x>>v[i].y;
        ys.pb(v[i].y);
    }
    sort(v.begin(),v.end());

    sort(ys.begin(),ys.end());
    ys.resize(unique(ys.begin(),ys.end()) - ys.begin());

    N = ys.size();
    max_seg.clear();
    min_seg.clear();

    max_seg.resize(2*N,-MOD);
    min_seg.resize(2*N,MOD);


    // pj, ... pi, ...

    // d(pj, pi) up = xi-xj + yj-yi = xi-yi + yj-xj
    // d(pj, pi) down = xi-xj + yi-yj = xi+yi - (xj+yj)

    ll ans = 0;
    for(int i=0;i<n;i++)
    {
        int cur_idx = lower_bound(ys.begin(),ys.end(),v[i].y) - ys.begin();
        if( i > 0 )
        {
            // for all points behind me j<i, that are above me yj > yi, I want max yj-xj
            ll mx = query(max_seg, 0, cur_idx, N-1);
            ans = max( ans, v[i].x-v[i].y + mx );

            // for all points behind me j<i, that are below me yj < yi, I want min yj+xj
            ll mn = query(min_seg, 1, 0, cur_idx);
            ans = max( ans, v[i].x+v[i].y - mn );
        }
        update(max_seg, 0, cur_idx, max( max_seg[cur_idx+N], v[i].y-v[i].x) );
        update(min_seg, 1, cur_idx, min( min_seg[cur_idx+N], v[i].y+v[i].x) );
    }
    cout<<ans,nl;

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Submission Info

Judge Result