In this HackerEarth Easy Queries problem solution, you are given an array of size N in which the value of the elements is either 0 or 1. All the elements of the array are numbered from position 0 to N - 1. You are given some queries which can be of the following 2 types.

0 index: In this type of query you have to find the nearest left and nearest right element from the position index in the array whose value is 1.
1 index: In this type of query you need to change the value at position index to 1 if its previous value is 0 or else leave it unchanged.


HackerEarth Easy Queries problem solution


HackerEarth Easy Queries problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll rn,n;
ll arr[100001];
ll block[1000][2];
ll find_right(ll index)
{

ll block_id = index/rn;
ll flag = 0;
if(block[block_id][1]>=1)
{
for(ll i=index;i<block_id*rn;i++)
{
if(arr[i]==1){
return i;
flag = 1;
break;}
}
}
if(flag==0)
{
block_id++;
while(!block[block_id][1]&&block_id<=(rn+1))
block_id+=1;

if(block_id<=(rn+1))
{
ll index1 = block_id*rn;
for(ll i =index1;i<=n;i++)
{
if(arr[i]==1){
return i;
break;}
}
}
}
return -1;
}
ll find_left(ll index)
{
ll block_id = index/rn;
ll flag = 0;
if(block[block_id][1]>=1)
{
for(ll i=index;i>=(block_id-1)*rn;i--)
{
if(arr[i]==1){
flag = 1;
return i;
break;}
}
}
if(flag==0)
{
block_id--;
while(!block[block_id][1]&&block_id>=0)
block_id-=1;
if(block_id>=0)
{
ll index1 = block_id*rn;
for(ll i=index1;i<=n;i++)
{
if(arr[i]==1){
return i;
break;}
}
}
}
return -1;
}
void update(ll index)
{
if(arr[index]==0)
{
arr[index] = 1;
block[index/rn][1]++;
block[index/rn][0]--;
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
ll m,block_id,type,value,ans1,ans2,i,q;
cin>>n>>q;
rn = sqrt(n);
for(i=0;i<=rn;i++)
block[i][0] = block[i][1] = 0;
for(i=0;i<n;i++)
cin>>arr[i];
block_id=-1;
for(i=0;i<n;i++)
{
if(i%rn==0)
block_id++;
if(arr[i]==0)
block[block_id][0]++;
else
block[block_id][1]++;
}
while(q--)
{
cin>>type>>value;
if(type==0)
{
ans1 = find_left(value);
ans2 = find_right(value);
cout<<ans1<<" "<<ans2<<endl;
}
else
{
update(value);
}
}
return 0;
}

Second solution

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
set<int> s;
int n , q;
cin >> n >> q;
assert(n >= 1 && n <= 100000);
assert(q >= 1 && q <= 100000);
for(int i = 0; i < n; i++)
{
int val;
cin >> val;
assert(val >= 0 && val <= 1);
if(val == 1)
s.insert(i);
}
while(q--)
{
int type , idx;
cin >> type >> idx;
assert(type >= 0 && type <= 1);
assert(idx >= 0 && idx < n);
if(type == 1)
{
s.insert(idx);
}
else
{
int ans_l = -1;
int ans_r = -1;
set<int>::iterator it_l = s.lower_bound(idx);
set<int>::iterator it_r = s.upper_bound(idx);
if(it_l != s.begin() && s.size())
{
--it_l;
ans_l = *(it_l);
}
if(it_r != s.end() && s.size())
{
ans_r = *(it_r);
}
cout << ans_l << " " << ans_r << endl;
}
}
}