Header Ad

HackerEarth Binary Modulo P2SME problem solution

In this HackerEarth Binary Modulo P2SME problem solution You are given a Binary String A of length N indexed from 0 to N - 1. You have to perform 2 queries:-
  1. 0 L R - Tell the remainder of the Number(in Decimal) represented by the Binary String between indexes L and R when divided by 5.
  2. 1 X V - Replace character at position X with V.

HackerEarth Binary Modulo <P2SME> problem solution


HackerEarth Binary Modulo <P2SME> problem solution.

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <math.h>

#define ll long long int
#define maxN 10000
#define maxVal 100000000
#define minVal -100000000
#define mod 1000000007LL

#define gcd(a,b) __gcd(a,b)

using namespace std;

struct data
{
int v,c;
};

int p[maxN+5];

int n;
char a[maxN+5];
data tree[3*maxN+5];

void pre()
{
int i;
p[0]=1;
for(i=1;i<=maxN;i++)
p[i]=(2*p[i-1])%5;
}

data makeNode(int v)
{
data x;
x.v=v;
x.c=1;
return x;
}

data combine(data l,data r)
{
data x;
x.v=((l.v*p[r.c])%5+r.v)%5;
x.c=l.c+r.c;
return x;
}

void build(int node,int start,int end)
{
if(start==end)
{
tree[node]=makeNode(a[start]-'0');
return;
}
int mid=start+(end-start)/2;
build(2*node+1,start,mid);
build(2*node+2,mid+1,end);
tree[node]=combine(tree[2*node+1],tree[2*node+2]);
}

data query(int node,int start,int end,int l,int r)
{
if(start>=l&&end<=r)
return tree[node];
int mid=start+(end-start)/2;
if(l>mid)
return query(2*node+2,mid+1,end,l,r);
if(r<=mid)
return query(2*node+1,start,mid,l,r);
return combine(query(2*node+1,start,mid,l,r),query(2*node+2,mid+1,end,l,r));
}

void update(int node,int start,int end,int i,int v)
{
if(start==end)
{
tree[node]=makeNode(v);
return;
}
int mid=start+(end-start)/2;
if(i<=mid)
update(2*node+1,start,mid,i,v);
else
update(2*node+2,mid+1,end,i,v);
tree[node]=combine(tree[2*node+1],tree[2*node+2]);
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,q,l,r,c;
pre();
scanf("%d",&t);
while(t--)
{
scanf("%s%d",a,&q);
n=strlen(a);
build(0,0,n-1);
while(q--)
{
scanf("%d%d%d",&c,&l,&r);
if(c==0)
printf("%d\n",query(0,0,n-1,l,r).v);
else
update(0,0,n-1,l,r);
}
}
return 0;
}


Post a Comment

0 Comments