HackerEarth Matrix problem solution

In this HackerEarth Matrix problem solution, All team is in the Matrix and need your help to escape!

Matrix is an infinite discrete world of square cells (x,y). There are some infinite height buildings and you have all records about them. The record (x,y) means that building occupies all cells (x',y') : x' = x,y'<=y. In other words, building is a one cell width strip which goes infinitely down. All buildings have pairwise distinct x coordinates.

There are q team members. For each team member you know his current cell and finish cell in which there is his exit from Matrix. Note that each team member should use his own exit and can't use exit of some other team member.

In one second each team member can go from cell (x,y) to any of cells (x + 1,y), (x - 1,y), (x,y - 1), (x,y + 1) if corresponding cell is not occupied by building. Once a person reaches cell with his exit, he can exit from the Matrix instantly.

For each team member you have to find minimum time which he needs to exit from the Matrix.

HackerEarth Matrix problem solution.

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <functional>
#include <sstream>
#include <fstream>
#include <valarray>
#include <complex>
#include <queue>
#include <cassert>
#include <bitset>
using namespace std;

#ifdef LOCAL
    #define debug_flag 1
#else
    #define debug_flag 0
#endif

template <class T1, class T2 >
std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) 
{
    os << "[" << p.first << ", " << p.second << "]";
    return os;
}

template <class T >
std::ostream& operator << (std::ostream& os, const std::vector<T>& v) 
{
    os << "[";
    bool first = true;
    for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
    {
        if (!first)
            os << ", ";
        first = false;
        os << *it;
    }
    os << "]";
    return os;
}

#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }

vector<string> _split(const string& s, char c) {
    vector<string> v;
    stringstream ss(s);
    string x;
    while (getline(ss, x, c))
        v.emplace_back(x);
    return v;
}

void _print(vector<string>::iterator) {}
template<typename T, typename... Args>
void _print(vector<string>::iterator it, T a, Args... args) {
    string name = it -> substr((*it)[0] == ' ', it -> length());
    if (isalpha(name[0]))
        cerr << name  << " = " << a << " ";
    else
        cerr << name << " ";
    _print(++it, args...);
}

typedef long long int int64;

const int pow2 = (1 << 19);
const int N = (int)1e6;
const int64 INF = (int64)1e18;

struct Tree {
  int64 max_val[pow2 * 2];

  Tree() {
    fill(max_val, max_val + 2 * pow2, -INF);
  }

  void relax_max(int pos, int64 val) {
    pos += pow2;
    max_val[pos] = max(max_val[pos], val);
    pos /= 2;
    while (pos >= 1) {
      max_val[pos] = max(max_val[pos * 2], max_val[pos * 2 + 1]);
      pos /= 2;
    }
  }

  bool not_inter(int l, int r, int a, int b) {
    return l > b || r < a;
  }

  bool is_in(int l, int r, int a, int b) {
    return a <= l && r <= b;
  }

  int64 get_max(int a, int b) {
    if (a > b) {
      return -INF;
    }
    return get_max(1, 0, pow2 - 1, a, b);
  }

  int64 get_max(int v, int l, int r, int a, int b) {
    if (not_inter(l, r, a, b)) {
      return -INF;
    }
    if (is_in(l, r, a, b)) {
      return max_val[v];
    }
    int m = (l + r) / 2;
    return max(get_max(v * 2, l, m, a, b),
        get_max(v * 2 + 1, m + 1, r, a, b));
  }
};

int n, q;
int64 x_list[N], y_list[N];
int64 sx_list[N], sy_list[N], fx_list[N], fy_list[N];

vector<int64> comp_list;
Tree tree;

int64 solve(int64 sx, int64 sy, int64 fx, int64 fy) {
  if (sx > fx) {
    swap(sx, fx);
    swap(sy, fy);
  }

  int a = lower_bound(comp_list.begin(), comp_list.end(), sx) - comp_list.begin();
  int b = upper_bound(comp_list.begin(), comp_list.end(), fx) - comp_list.begin() - 1;
  int64 mx_between = tree.get_max(a, b);

  int64 dist = fx - sx;
  if (sy <= mx_between) {
    dist += mx_between + 1 - sy;
    sy = mx_between + 1;
  }
  dist += abs(sy - fy);

  return dist;
}

int main()
{
#ifdef LOCAL
    freopen ("input.txt", "r", stdin);
#endif

  scanf("%d%d", &n, &q);
  for (int i = 0; i < n; i++) {
    scanf("%lld%lld", &x_list[i], &y_list[i]);
  }
  for (int i = 0; i < q; i++) {
    scanf("%lld%lld%lld%lld", &sx_list[i], &sy_list[i], &fx_list[i], &fy_list[i]);
  }

  for (int i = 0; i < n; i++) {
    comp_list.push_back(x_list[i]);
  }
  sort(comp_list.begin(), comp_list.end());
  comp_list.erase(unique(comp_list.begin(), comp_list.end()), comp_list.end());

  for (int i = 0; i < n; i++) {
    int pos = lower_bound(comp_list.begin(), comp_list.end(), x_list[i]) - comp_list.begin();
    tree.relax_max(pos, y_list[i]);
  }

  for (int i = 0; i < q; i++) {
    printf("%lld\n", solve(sx_list[i], sy_list[i], fx_list[i], fy_list[i]));
  }

    return 0;
}