HackerEarth Mr. Sinister and his World problem solution

YASH PAL,
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

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 100005

using 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-ordinate


void 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 %dn",ans,lef,rt);
            }
        }

    }
    return  0;

}

Second solution

#include <bits/stdc++.h>
#define MAX 1000005
#define INF 1000000000

using 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);
            }
            
        }
        
    }
}
coding problems solutions