# HackerEarth Mr. Sinister and his World problem solution

In this HackerEarth Mr. Sinister and his World problem solution, It is a very bad time for human race, as powerful mutant Mr. Sinister has taken control of the world. He is killing a lot of people. The world is one dimensional and at most one man can stay at one point of the world. The points are numbered from (1,0) to (I N F, 0) where I N F denotes infinity.

As Sinister is killing humans, he wants to know the maximum distance between any two adjacent humans in the world. But a human can come or leave the world (goes to another planet) at a time. So, there will be three types of queries of the following form.

1 X - A human comes and occupies co-ordinate (X,0). It is guaranteed that before this query, there will be no human at the given point.

2 - You have to find out the maximum distance between any two adjacent humans and the position of these two humans. If there is a tie in the maximum adjacent distances, then print the one which has maximum X coordinates.

## HackerEarth Mr. Sinister and his World problem solution.

`#include <bits/stdc++.h>#define FOR(i, s, e) for(int i=s; i<e; i++)#define loop(i, n) for(int i=0; i<n; i++)#define CIN   ios_base::sync_with_stdio(0); cin.tie(0)#define getint(n) scanf("%d", &n)#define pb(a) push_back(a)#define ll long long int#define ull unsigned long long int#define dd double#define SZ(a) int(a.size())#define read() freopen("input.txt", "r", stdin)#define write() freopen("output.txt", "w", stdout)#define mem(a, v) memset(a, v, sizeof(a))#define all(v) v.begin(), v.end()#define pi acos(-1.0)#define pf printf#define sf scanf#define mp make_pair#define paii pair<int, int>#define padd pair<dd, dd>#define pall pair<ll, ll>#define fr first#define sc second#define CASE(n) printf("Case %d:\n",++n)#define CASE_COUT cout<<"Case "<<++cas<<": "#define inf 1000000000#define EPS 1e-9#define Harmonic(n) (0.577215664901532+log(n)+(1/(2*n)))     ///Use Only for large n#define mx 100005using namespace std;int SET(int n,int pos){ return n=n | (1<<pos);}int RESET(int n,int pos){ return n=n & ~(1<<pos);}int CHECK(int n,int pos){ return (bool) (n & (1<<pos));}int str2int(string s) {    stringstream ss(s);    int x;    ss >> x;    return x;}string int2str(int a) {    stringstream ss;    ss << a;    string str = ss.str();    return str;}string char2str(char a) {    stringstream ss;    ss << a;    string str = ss.str();    return str;}ll bigMod(ll n,ll power,ll MOD){    if(power==0)        return 1;    if(power%2==0)    {        ll ret=bigMod(n,power/2,MOD);        return ((ret%MOD)*(ret%MOD))%MOD;    }    else return ((n%MOD)*(bigMod(n,power-1,MOD)%MOD))%MOD;}ll modInverse(ll n,ll MOD){    return bigMod(n,MOD-2,MOD);}int POW(int x, int y){    int res= 1;    for ( ; y ; ) {        if ( (y&1) ) {            res*= x;        }        x*=x;        y>>=1;    }    return res;}int inverse(int x){    dd p=((dd)1.0)/x;    return (p)+EPS;}int gcd(int a, int b){    while(b) b^=a^=b^=a%=b;    return a;}int nC2(int n){    return n*(n-1)/2;}ll MOD(ll n,ll mod){    if(n>=0)        return n%mod;    else if(-n==mod)        return 0;    else        return mod+(n%mod);}int n,tree[1000005],data[100005];set< pair< int, paii > >sata;       ///This will hold the distance and co-ordinatevoid update(int i,int val)          ///Update the BIT{    while(i<=1000000)    {        tree[i]+=val;        i+=i & (-i);    }}int query(int i)                    ///Query{    int sum=0;    while(i>0)    {        sum+=tree[i];        i-=i & (-i);    }    return sum;}int leftIndex(int id)               ///Find out the nearest co-ordinate left side of the given point{    if(query(id)==0) return -1;     ///If there is no point in the left  return -1    int lo=1;    int hi=id;    int mid=(lo+hi)/2;    int ans;    while(lo<=hi)    {        int pp=query(id)-query(mid-1);        if(pp>=1)        {            ans=mid;            lo=mid+1;        }        else            hi=mid-1;        mid=(lo+hi)/2;    }    return ans;}int rightIndex(int id)              ///Find out the nearest index right side of the given point{    if(query(1000000)-query(id-1)==0) return -1;    ///If there is no point in the right  return -1    int lo=id;    int hi=1000000;    int mid=(lo+hi)/2;    int ans;    while(lo<=hi)    {        int pp=query(mid)-query(id-1);        if(pp>=1)        {            hi=mid-1;            ans=mid;        }        else            lo=mid+1;        mid=(lo+hi)/2;    }    return ans;}int main(){    int t,cas=0;    cin>>t;    assert(t>=1 && t<=5);    while(t--)    {        mem(tree,0);        sata.clear();        cin>>n;        assert(n>=2 && n<=100000);        loop(i,n)        {            int p;            cin>>p;            assert(p>=1 && p<=1000000);            update(p,1);                ///Update the new point on BIT            data[i]=p;        }        sort(data,data+n);        for(int i=0;i<n-1;i++)        {            sata.insert(mp(data[i+1]-data[i],mp(data[i],data[i+1])));   /// put all the distance and their co-ordinate. It will be sorted        }        int q;        cin>>q;        assert(q>=1 && q<=100000);        CASE(cas);        while(q--)        {            int type;            cin>>type;            if(type==1)             ///Insert            {                int x;                cin>>x;                assert(x>=1 && x<=1000000);                int index1=leftIndex(x);                int index2=rightIndex(x);                if(index1!=-1 && index2!=-1)                 {                    sata.erase(mp(index2-index1,mp(index1,index2)));                    sata.insert(mp(x-index1,mp(index1,x)));                    sata.insert(mp(index2-x,mp(x,index2)));                }                else if(index1==-1 && index2!=-1)                {                    sata.insert(mp(index2-x,mp(x,index2)));                }                else if(index1!=-1 && index2==-1)                {                    sata.insert(mp(x-index1,mp(index1,x)));                }                update(x,1);            }            else if(type==3)        ///Delete            {                int x;                cin>>x;                assert(x>=1 && x<=1000000);                int index1=leftIndex(x-1);                int index2=rightIndex(x+1);                if(index1!=-1 && index2!=-1)            ///Remove the previous point adjacent to the given point and put new                {                    sata.erase(mp(x-index1,mp(index1,x)));                    sata.erase(mp(index2-x,mp(x,index2)));                    sata.insert(mp(index2-index1,mp(index1,index2)));                }                else if(index1==-1 && index2!=-1)                {                    sata.erase(mp(index2-x,mp(x,index2)));                }                else if(index1!=-1 && index2==-1)                {                    sata.erase(mp(x-index1,mp(index1,x)));                }                update(x,-1);            }            else            {                auto it=sata.rbegin();                int lef=it->sc.fr;                 int rt=it->sc.sc;                int ans=rt-lef;                pf("%d %d %d\n",ans,lef,rt);            }        }    }    return  0;}`

### Second solution

`#include <bits/stdc++.h>#define MAX 1000005#define INF 1000000000using namespace std;int A[MAX];bool vis[MAX];set < pair <int, int> > s;struct node {    int mx;    int mn;    node() { }    node(int mx, int mn) {        this->mx = mx, this->mn = mn;    }}tree[4*MAX];node combine(node a, node b){    return node(max(a.mx,b.mx), min(a.mn, b.mn));    }void build(int where, int left, int right){    if ( left > right ) return;    if ( left == right ) {        if ( vis[left] ) tree[where].mx = tree[where].mn = left;        else tree[where].mx = 0, tree[where].mn = INF;        return;    }    int mid = (left + right)/2;    build(where*2, left, mid);    build(where*2 + 1, mid + 1, right);    tree[where] = combine(tree[where*2], tree[where*2 + 1]);}void update(int where, int left, int right, int idx){    if ( left > right || left > idx || right < idx ) return;    if ( left == right ) {        if ( vis[left] ) tree[where].mx = tree[where].mn = left;        else tree[where].mx = 0, tree[where].mn = INF;        return;    }    int mid = (left + right)/2;    update(where*2, left, mid, idx);    update(where*2 + 1, mid + 1, right, idx);    tree[where] = combine(tree[where*2], tree[where*2 + 1]);}node query(int where, int left, int right, int i, int j){    if ( left > right || left > j || right < i ) return node(0, INF);    if ( left >= i && right <= j ) return tree[where];    int mid = (left + right)/2;    return combine(query(where*2, left, mid, i, j), query(where*2 + 1, mid + 1, right, i, j));}void add(int x){    node ryt = query(1, 1, 1000000, x + 1, 1000000);    node lft = query(1, 1, 1000000, 1, x - 1);        int right_val = ryt.mn;    int left_val = lft.mx;        if ( right_val == INF ) {        s.insert(make_pair(x - left_val, left_val));    }    else if ( right_val == tree[1].mn ) {        s.insert(make_pair(right_val - x, x));    }    else {        s.erase(make_pair(right_val - left_val, left_val));        s.insert(make_pair(x - left_val, left_val));        s.insert(make_pair(right_val - x, x));    }    update(1, 1, 1000000, x);}void _remove(int x){    node ryt = query(1, 1, 1000000, x + 1, 1000000);    node lft = query(1, 1, 1000000, 1, x - 1);        int right_val = ryt.mn;    int left_val = lft.mx;        if ( right_val == INF ) {        s.erase(make_pair(x - left_val, left_val));    }    else {        if ( left_val == 0 ) {            s.erase(make_pair(right_val - x, x));        }        else {            s.erase(make_pair(x - left_val, left_val));            s.erase(make_pair(right_val - x, x));            s.insert(make_pair(right_val - left_val, left_val));        }    }    update(1, 1, 1000000, x);}int main(){    int t, n, x, q, type, tot;        cin >> t;    assert(t >= 1 && t <= 3);        for ( int tc = 1; tc <= t; tc++ ) {                cin >> n;        assert(n >= 2 && n <= 100000);                tot = n;        for ( int i = 1; i <= 1000000; i++ ) vis[i] = false;                for ( int i = 0; i < n; i++ ) {            cin >> A[i];            assert(A[i] >= 1 && A[i] <= 1000000);            vis[A[i]] = true;        }                build(1, 1, 1000000);                sort(A, A + n);                s.clear();                for ( int i = 1; i < n; i++ ) {            assert(A[i] != A[i - 1]);            s.insert(make_pair(A[i] - A[i - 1], A[i - 1]));        }                cout << "Case " << tc << ":" << endl;        cin >> q;        assert(q >= 1 && q <= 100000);                while ( q-- ) {                        cin >> type;            assert(type >= 1 && type <= 3);                        if ( type == 1 ) {                cin >> x;                assert(x >= 1 && x <= 1000000);                assert(vis[x] == false);                tot++;                vis[x] = true;                add(x);            }            else if ( type == 2 ) {                set < pair <int, int> > :: reverse_iterator it = s.rbegin();                cout << it->first << " " << it->second << " " << it->first + it->second << endl;            }            else {                cin >> x;                assert(tot >= 2);                assert(x >= 1 && x <= 1000000);                assert(vis[x] == true);                tot--;                vis[x] = false;                _remove(x);            }                    }            }}`