HackerEarth Reunion of 1’s problem solution

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’).

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