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. #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 %dn",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); } } }} coding problems