HackerEarth Easy Queries problem solution

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.

#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;
                    }
            }
    }

coding problems solutions