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 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 %d\n",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);
}
}
}
}
0 Comments