HackerEarth Reunion of 1's problem solution

In this HackerEarth Reunion of 1's problem solution, You are given a string of size n consisting of 0s and/or 1s. You have to perform total k queries and there are two types of queries possible:

1. "1" (without quotes): Print length of the longest sub-array which consists of all '1'.
2. "2 X" (without quotes): where X is an integer between 1 to n. In this query, you will change character at the Xth position to '1' (It is possible that the character at i-th position was already '1').

HackerEarth Reunion of 1's problem solution.

#include <bits/stdc++.h>
using namespace std;
 
#define ms(s, n) memset(s, n, sizeof(s))
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FORd(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FORall(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define sz(a) int((a).size())
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vii;
const int MOD = (int) 1e9 + 7;
const int INF = (int) 1e9;
const ll LINF = (ll) 1e18;
const ld PI = acos((ld) -1);
const ld EPS = 1e-9;
ll gcd(ll a, ll b) {ll r; while (b) {r = a % b; a = b; b = r;} return a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll fpow(ll n, ll k, int p = MOD) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = r * n % p; n = n * n % p;} return r;}
template<class T> void setmin(T& a, T val) {if (a > val) a = val;}
template<class T> void setmax(T& a, T val) {if (a < val) a = val;}
void addmod(int& a, int val, int p = MOD) {if ((a = (a + val)) >= p) a -= p;}
void submod(int& a, int val, int p = MOD) {if ((a = (a - val)) < 0) a += p;}
int mult(int a, int b, int p = MOD) {return (ll) a * b % p;}
int inv(int a, int p = MOD) {return fpow(a, p - 2, p);}

int a[1000005],keep[1000005],size[1000005];
int ans;
int root(int i)
{
    while(keep[ i ] != i)         
        i = keep[ i ];
    
    return i;
}
void unio(int A,int B)
{
    int AA = root(A);
    int BB = root(B);
    if(size[AA] < size[BB ])
    {
        keep[ AA ] = keep[BB];
        size[BB] += size[AA];
    }
    else
    {
        keep[ BB ] = keep[AA];
        size[AA] += size[BB];
    }

}
bool find(int A,int B)
{
    if( root(A)==root(B) )      
    return true;
    else
    return false;
}
void update(int num)
{
    if(a[num])return ;
    a[num] = 1;
    size[num] = 1;
    keep[num] = num;
    
    if(a[num-1])
        unio(num,num-1);
    if(a[num+1])
        unio(num,num+1);
    
    ans = max(ans,size[root(num)]);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    ll n,q;cin>>n>>q;
    string str;cin>>str;
    
    FOR(i,0,str.length())
    {
        if(str[i]=='1')
        {
            update(i+1);
        }
    }
    
    while(q--)
    {
        int type;cin>>type;
        if(type==1)
        cout<<ans<<"\n";
        else
        {
            int num;cin>>num;
            update(num);
        }
        
    }

    return 0;
}

Second solution

#include<bits/stdc++.h>
using namespace std;
int n,q,maxx;
int par[100005],size[100005];
int find(int x)
{
    if(x==par[x])return par[x];
    return par[x]=find(par[x]);
}
void unionset(int a,int b)
{
    int para=find(a);
    int parb=find(b);
    if(para==parb)return;
    if(size[para]<size[parb])
    {
        par[para]=parb;
        size[parb]+=size[para];
        maxx=max(maxx,size[parb]);
    }
    else
    {
        par[parb]=para;
        size[para]+=size[parb];
        maxx=max(maxx,size[para]);
    }
}
int main()
{
    cin>>n>>q;
    string s;
    cin>>s;s="0"+s+"0";
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1')
        {
            size[i]=1;par[i]=i;maxx=1;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1')
        {
            if(s[i-1]=='1')unionset(i-1,i);
            //if(s[i+1]=='1')unionset(i,i+1);
        }
    }
    while(q--)
    {
        int type;
        cin>>type;
        if(type==1)cout<<maxx<<"\n";
        else
        {
            int ind;
            cin>>ind;
            if(s[ind]=='1')continue;
            s[ind]='1';size[ind]=1;par[ind]=ind;maxx=max(maxx,1);
            if(s[ind-1]=='1'){unionset(ind-1,ind);}
            if(s[ind+1]=='1')unionset(ind,ind+1);
        }
    }
    return 0;
}