HackerEarth Mathison and the furthest point solution

In this HackerEarth Mathison and the furthest point problem solution Mathison has taken a course in Computational Geometry. He managed to solve almost all problems from his latest problem sheet. The hardest one was sent to you and is described below.

You are given a C x C grid that currently contains no active points and on which you can perform certain operations.

An operation can be an activation (x,y), in which so you mark the point at coordinates (x,y) as active if the point was not already marked. Otherwise, you do nothing.

The second type of operation is a query (x,y) (x1,y1) (x2,y2): you have to find the greatest manhattan distance between the point and any active point that lies inside the rectangle with the bottom-left corner in (x1,y1) and the top-right one in (x2,y2).

You are given N such operations and you have to execute them all!

HackerEarth Mathison and the furthest point problem solution.

#include <bits/stdc++.h>

using namespace std;

using Point = pair<int,int>;

int man_dist(const Point &A, const Point &B){
  return abs(A.first - B.first) + abs(A.second - B.second);
}

bool in_interval(int p, int x, int y){
  return x <= p && p <= y;
}

bool in_rectangle(Point p, int x1, int x2, int y1, int y2){
  return in_interval(p.first, x1, x2) &&
         in_interval(p.second, y1, y2);
}

int main(){
  ios_base::sync_with_stdio(false);

  set<Point> points;

  int N;
  cin >> N;

  while (N--){
    int t;
    cin >> t;

    // update
    if (t == 0){
      int x, y;
      cin >> x >> y;
      points.insert({x, y});
    }
    else{
      int x, y, x1, y1, x2, y2;
      cin >> x >> y >> x1 >> y1 >> x2 >> y2;

      int answer = -1;

      for (auto p: points)
        if (in_rectangle(p, x1, x2, y1, y2)){
          answer = max(answer, man_dist(p, {x, y}));
        }

      if (answer == -1)
        cout << "no point!\n";
      else
        cout << answer << "\n";
    }
  }

  return 0;
}

Second solution

#include "bits/stdc++.h"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int oo = 1e9 + 6669;
struct cc
{
    int maxsum,minsum,maxdiff,mindiff;
};
const cc M = {-oo,oo,-oo,oo};
cc min(cc a,cc b)
{
    return {max(a.maxsum,b.maxsum),min(a.minsum,b.minsum),max(a.maxdiff,b.maxdiff),min(a.mindiff,b.mindiff)};
}
struct tt
{
    tt *l,*r;
    cc ans;
    void up(void)
    {
        ans = M;
        if (l) ans = min(ans,l->ans);
        if (r) ans = min(ans,r->ans);
    }
    tt() : l(0),r(0) {ans = M;}
};
typedef tt * tr;
const int N = (int)(1e6) + 5;
tr s[N];
int h,w;
void upA(int p,int u,int x,int y,int pos,tr& node)
{
    if (!node) node = new tt();
    if (p == u) return void(node->ans = min(node->ans,cc{x + y,x + y,x - y,x - y}));
    int m = (p + u) / 2;
    if (pos <= m) upA(p,m,x,y,pos,node->l);
    else upA(m+1,u,x,y,pos,node->r);
    node->up();
}
cc queryA(int p,int u,int l,int r,tr node)
{
    if (!node) return M;
    if (l <= p && u <= r) return node->ans;
    int m = (p + u) / 2;
    auto ans = M;
    if (l <= m) ans = min(ans,queryA(p,m,l,r,node->l));
    if (m+1<=r) ans = min(ans,queryA(m+1,u,l,r,node->r));
    return ans;
}
void upB(int p,int u,int pos1,int pos2,int x,int y,int node)
{
    upA(1,w,x,y,pos2,s[node]);
    if (p == u) return;
    int m = (p + u) / 2;
    if (pos1 <= m) upB(p,m,pos1,pos2,x,y,node << 1);
    else upB(m+1,u,pos1,pos2,x,y,node << 1 | 1);
}
cc queryB(int p,int u,int l1,int r1,int l2,int r2,int node)
{
    if (l1 <= p && u <= r1) return queryA(1,w,l2,r2,s[node]);
    int m = (p + u) / 2;
    auto ans = M;
    if (l1 <= m) ans = min(ans,queryB(p,m,l1,r1,l2,r2,node << 1));
    if (m+1<=r1) ans = min(ans,queryB(m+1,u,l1,r1,l2,r2,node << 1 | 1));
    return ans;
}
inline int readChar();
template <class T = int> inline T readInt();
template <class T> inline void writeInt( T x, char end = 0 );
inline void writeChar( int x );
inline void writeWord( const char *s );

/** Read */

static const int buf_size = 4096;

inline int getChar() {
    static char buf[buf_size];
    static int len = 0, pos = 0;
    if (pos == len)
        pos = 0, len = fread(buf, 1, buf_size, stdin);
    if (pos == len)
        return -1;
    return buf[pos++];
}

inline int readChar() {
    int c = getChar();
    while (c <= 32)
        c = getChar();
    return c;
}

template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}

/** Write */

static int write_pos = 0;
static char write_buf[buf_size];

inline void writeChar( int x ) {
    if (write_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
    write_buf[write_pos++] = x;
}

template <class T>
inline void writeInt( T x, char end ) {
    if (x < 0)
        writeChar('-'), x = -x;

    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}

inline void writeWord( const char *s ) {
    while (*s)
        writeChar(*s++);
}

struct Flusher {
    ~Flusher() {
        if (write_pos)
            fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
    }
} flusher;

int main(void)
{
    int n;
    n = readInt();
    vi sx,sy;
    vector < vi > queries;
    for (int i = 0;i < n;++i)
    {
        int op,x,y;
        op = readInt();
        x = readInt();
        y = readInt();
        sx.pb(x);
        sy.pb(y);
        if (!op)
            queries.pb({op,x,y});
        else
        {
            int a,b,c,d;
            a = readInt();
            b = readInt();
            c = readInt();
            d = readInt();
            queries.pb({op,x,y,a,b,c,d});
        }
    }
    sort(all(sx));
    sort(all(sy));
    sx.resize(unique(all(sx)) - sx.begin());
    sy.resize(unique(all(sy)) - sy.begin());
    h = sx.size();
    w = sy.size();
    set < pii > was;
    for (auto Query : queries)
    {
        int x = Query[1];
        int y = Query[2];
        int x1 = lower_bound(all(sx),x) - sx.begin() + 1;
        int y1 = lower_bound(all(sy),y) - sy.begin() + 1;
        if (!Query[0])
        {
            if (!was.count(mp(x,y)))
                upB(1,h,x1,y1,x,y,1);
            was.insert(mp(x,y));
        }
        else
        {
            int a = lower_bound(all(sx),Query[3]) - sx.begin() + 1;
            int b = lower_bound(all(sy),Query[4]) - sy.begin() + 1;
            int c = lower_bound(all(sx),Query[5] + 1) - sx.begin();
            int d = lower_bound(all(sy),Query[6] + 1) - sy.begin();
            if (!(a <= c && b <= d))
            {
                writeWord("no point!\n");
                continue;
            }
            int ans = -oo;
            int l1,r1,l2,r2;
            l1 = max(a,x1);r1 = max(b,y1);l2 = c;r2 = d;
            if (l1 <= l2 && r1 <= r2)
                ans = max(ans,queryB(1,h,l1,l2,r1,r2,1).maxsum - x - y);
            l1 = a;r1 = b;l2 = min(x1,c);r2 = min(y1,d);
            if (l1 <= l2 && r1 <= r2)
                ans = max(ans,x + y - queryB(1,h,l1,l2,r1,r2,1).minsum);
            l1 = a;r1 = max(y1,b);l2 = min(x1,c);r2 = d;
            if (l1 <= l2 && r1 <= r2)
                ans = max(ans,x - y - queryB(1,h,l1,l2,r1,r2,1).mindiff);
            l1 = max(a,x1);r1 = b;l2 = c;r2 = min(y1,d);
            if (l1 <= l2 && r1 <= r2)
                ans = max(ans,queryB(1,h,l1,l2,r1,r2,1).maxdiff - (x - y));
            if (ans < 0)
                writeWord("no point!\n");
            else
                writeInt(ans,'\n');
        }
    }
    return 0;
}