In this HackerRank Jaggu Playing with Balloons problem solution you are given q number of queries which can be either an Update Query or Report Query.Each Update Query is followed by at least 1 report query. for each query we need to output the answer in a separate line.
Problem solution in Java Programming.
import java.util.*;
import java.io.*;
public class JagguWaterBall {
static long[] buckets = null;
static void go() {
int q = in.nextInt();
buckets = new long[1000002];
while (q-- > 0) {
String command = in.nextString();
if (command.charAt(0) == 'U') {
int p = in.nextInt();
int m = in.nextInt();
int plus = in.nextInt();
update(p, m, plus);
} else {
int p1 = in.nextInt();
int p2 = in.nextInt();
//out.println(read(p2) - read(p1-1));
out.println(getBetween(p1-1, p2));
}
}
}
static void update(int pos, int m, int plus) {
int N = 1000000; //1 million
for (int i = 1; i <= 50; i++) {
//System.out.println("i= " + i);
int back = pos;
//System.out.println("start pos = " + pos);
for (int j = 1; j <= 1000; j++) {
//System.out.println("pos1 = " + pos);
//buckets[pos] += m;
add(pos, m);
int s, in = getBITs(pos);
for (int k = 0; ; k++) {
//System.out.println("k = " + k);
s = pos + (1<<k);
if (getBITs(s) <= in) {
in = getBITs(s);
pos = s;
if (pos > N) {
//System.out.println("pos = " + pos);
break;
}
//System.out.println("pos2 = " + pos);
//buckets[pos] += m;
add(pos, m);
}
}
//System.out.println(" j = " + j + ": " + pos);
pos = pos - N;
if (pos == 48576 && j < 1000) {
long val = (1000 - j) * m;
add(48576, val);
add(48640, val);
add(49152, val);
add(65536, val);
add(131072, val);
add(262144, val);
add(524288, val);
break;
}
}
pos = back + plus;
//System.out.println("pos3 = " + pos);
if (pos > N)
pos -= N;
}
}
static long getBetween(int p1, int p2) {
long ret = 0;
while(p1 != p2) {
if (p2 > p1) {
ret += buckets[p2];
p2 -= (p2 & -p2);
} else {
ret -= buckets[p1];
p1 -= (p1 & -p1);
}
}
return ret;
}
static long read(int idx) {
long sum = 0;
while(idx > 0) {
sum += buckets[idx];
idx -= (idx & -idx);
}
return sum;
}
static void add(int idx, long x) {
while(idx <= 1000000) {
buckets[idx] += x;
idx += (idx & -idx);
}
}
static int getBITs(long x) {
int ret = 0;
while (x > 0) {
ret++;
x &= x - 1;
}
return ret;
}
static InputReader in;
static PrintWriter out;
public static void main(String[] args) {
in = new InputReader(System.in);
out = new PrintWriter(System.out);
go();
out.close();
}
static class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1)
throw new InputMismatchException();
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0)
return -1;
}
return buf[curChar++];
}
public int nextInt() {
return (int) nextLong();
}
public long nextLong() {
int c = read();
while (isSpaceChar(c))
c = read();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9')
throw new InputMismatchException();
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String nextString() {
int c = read();
while (isSpaceChar(c))
c = read();
StringBuilder sb = new StringBuilder(1024);
do {
sb.append((char) c);
c = read();
} while (!isSpaceChar(c));
return sb.toString();
}
public static boolean isSpaceChar(int c) {
switch (c) {
case -1:
case ' ':
case '\n':
case '\r':
case '\t':
return true;
default:
return false;
}
}
}
}Problem solution in C++ programming.
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<assert.h>
using namespace std;
#define MaxN 1000000
#define rep1 50
#define rep2 1000
#define MaxVal MaxN
typedef long long int ll;
int special[]={1,983041,999425,999937,1000001};
int bouncedat[]={48576,15808,448,64};
ll tree[MaxN+1];
ll read(int pos)
{
ll sum=0;
while(pos){
sum = sum + tree[pos];
pos-=(pos&(-pos));
}
return sum;
}
void update(int pos,ll v)
{
ll b=v;
while(pos<=MaxVal){
tree[pos]+=v;
v+=b;
pos+=(pos&(-pos));
}
}
int main()
{
int N=MaxN,Q,x,y,plus,j,counter[4],where;
char ch;
scanf("%d",&Q);
for(int i=0;i<Q;i++){
scanf(" %c%d%d",&ch,&x,&y);
if(ch=='U'){
where=0;
scanf("%d",&plus);
memset(counter,0,sizeof(counter));
for(j=1;j<=rep1;j++){
update(x,y);
if(x>=special[where] && x<special[where+1]) counter[where]++;
else{
while(1){
where++;
if(where==4) where=0;
if(x>=special[where] && x<special[where+1]){
counter[where]++;
break;
}
}
}
x=x+plus;
if(x>N) x=x-N;
}
for(j=0;j<4;j++){
if(counter[j]!=0)
update(bouncedat[j],y*(counter[j]));
}
update(bouncedat[0],(ll)y*(ll)(rep2-2)*(ll)rep1);
}
else printf("%lld\n",read(y)-read(x-1));
}
return 0;
}Problem solution in C programming.
#include<stdio.h>
int arr[]={1,983041,999425,999937,1000001};
int ar1[]={48576,15808,448,64};
long long int ar2[1000001];
long long int ans(int a)
{
long long int sum=0;
while(a)
{
sum = sum + ar2[a];
a-=(a&(-a));
}
return sum;
}
void query(int a,long long int b)
{
long long int c=b;
while(a<=1000000)
{
ar2[a]+=b;
b+=c;
a+=(a&(-a));
}
}
int main()
{
int i,N=1000000,Q,pos1,pos2,plus,j,temp;
char qry;
scanf("%d",&Q);
for(i=0;i<Q;i++){
scanf(" %c",&qry);
scanf("%d %d",&pos1,&pos2);
if(qry =='U'){
temp=0;
int counter[4]={0};
scanf("%d",&plus);
for(j=1;j<=50;j++)
{
query(pos1,pos2);
if(pos1>=arr[temp] && pos1<arr[temp+1])
counter[temp]++;
else
{
while(1)
{
temp++;
if(temp==4)
temp=0;
if(pos1>=arr[temp] && pos1<arr[temp+1])
{
counter[temp]++;
break;
}
}
}
pos1=pos1+plus;
if(pos1>N)
pos1=pos1-N;
}
for(j=0;j<4;j++){
if(counter[j]!=0)
query(ar1[j],pos2*(counter[j]));
}
query(ar1[0],(long long int)pos2*49900);
}
else
printf("%lld\n",ans(pos2)-ans(pos1-1));
}
return 0;
}
0 Comments