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


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