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("%lldn",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("%lldn",ans(pos2)-ans(pos1-1)); } return 0; }