Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth Mr. Sinister and his World problem solution

YASH PAL, 31 July 2024
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

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes