Jaggu Playing with Balloons

                            Solution in C :

In    C++  :










#include<iostream>
#include<string>
using namespace std;

long long tree[1000001];
int bitcount[2000001];

void init()
{
for (int i = 0; i <= 2000000; i++)
for (int j = 0; j < 32; j++)
if (i&(1 << j))
bitcount[i]++;
}

void update(int idx, int val)
{
while (idx <= 1000000)
{
tree[idx] += val;
idx += (idx & -idx);
}
}

long long read(int idx)
{
long long sum = 0;
while (idx > 0)
{
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}

void update(int pos, int M, int plus)
{
int N = 1000000;
for (int i = 1; i <= 50; i++)
{
int back = pos, j;
for (j = 1; j <= 1000; j++)
{
int s, in = bitcount[pos];
if (pos == 48576) break;
update(pos, M);
for (int k = 0;; k++)
{
s = pos + (k == 0 ? 1 : (1 << (k - 1)));
if (bitcount[s] <= in)
{
in = bitcount[s];
pos = s;
if (pos > N) break;
update(pos, M);
}
}
pos -= N;
}

update(48576, (1000 - j + 1) * M);
update(48640, (1000 - j + 1) * M);
update(49152, (1000 - j + 1) * M);
update(65536, (1000 - j + 1) * M);
update(131072, (1000 - j + 1) * M);
update(262144, (1000 - j + 1) * M);
update(524288, (1000 - j + 1) * M);

pos = back + plus;
if (pos > N) pos -= N;
}
}

int main()
{
int q;
cin >> q;
init();
while (q--)
{
char ch;
cin >> ch;
if (ch == 'U')
{
int pos, M, plus;
cin >> pos >> M >> plus;
update(pos, M, plus);
}
else
{
int pos1, pos2;
cin >> pos1 >> pos2;
long long sum1 = read(pos1 - 1);
long long sum2 = read(pos2);
cout << sum2 - sum1 << endl;
}
}
return 0;
}










In   Java  :








import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class Solution {

    public static void solve(Input in, PrintWriter out) 
throws IOException {
        int n = 1000000;
        int[] next = new int[n];
        int[] next2 = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            next[i] = i | (i + 1);
            if (next[i] >= n) {
                next2[i] = next[i] - n;
            } else {
                next2[i] = next2[next[i]];
            }
        }
        long[] f = new long[n];
        int qs = in.nextInt();
        for (int q = 0; q < qs; ++q) {
            if (in.next().equals("U")) {
                int pos = in.nextInt() - 1;
                long m = in.nextLong();
                int add = in.nextInt();
                for (int it = 0; it < 50; ++it) {
                    int x = (pos + it * add) % n;
                    int incs = 1000;
                    while (incs > 0) {
                        if (next2[x] == x) {
                            inc(x, m * incs, f);
                            incs = 0;
                        } else {
                            inc(x, m, f);
                            --incs;
                            x = next2[x];
                        }
                    }
                }
            } else {
                int pos1 = in.nextInt() - 1;
                int pos2 = in.nextInt() - 1;
                out.println(get(pos2, f) - get(pos1 - 1, f));
            }
        }
    }

    private static long get(int x, long[] f) {
        long r = 0;
        while (x >= 0) {
            r += f[x];
            x = (x & (x + 1)) - 1;
        }
        return r;
    }

    private static void inc(int x, long m, long[] f) {
        long add = m;
        while (x < f.length) {
            f[x] += add;
            add += m;
            x = x | (x + 1);
        }
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(System.out);
        solve(new Input(new BufferedReader(
new InputStreamReader(System.in))), out);
        out.close();
    }

    static class Input {
        BufferedReader in;
        StringBuilder sb = new StringBuilder();

        public Input(BufferedReader in) {
            this.in = in;
        }

        public Input(String s) {
            this.in = new BufferedReader(new StringReader(s));
        }

        public String next() throws IOException {
            sb.setLength(0);
            while (true) {
                int c = in.read();
                if (c == -1) {
                    return null;
                }
                if (" \n\r\t".indexOf(c) == -1) {
                    sb.append((char)c);
                    break;
                }
            }
            while (true) {
                int c = in.read();
                if (c == -1 || " \n\r\t".indexOf(c) != -1) {
                    break;
                }
                sb.append((char)c);
            }
            return sb.toString();
        }

        public int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        public long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
    }
}











In    C  :








#include<stdio.h>

int i,j,k,n,m,pos,plus,pos1,pos2,q,t,back;
long long a[1111111];
char c;

int lowbit(int i) {
return i & -i;
}

void update(int index, int delta) {
for (int i = index; i <= 1000000; i += lowbit(i))
a[i] += delta;
}

long long sum(int index) {
long res = 0;
for (; index > 0; index -= lowbit(index))
res += a[index];
return res;
}

main()
{
scanf("%d",&q);
for (t=1; t<=q; t++)
{
scanf("%c",&c);
while (c!='R' && c!='U') scanf("%c",&c);
if (c=='R') scanf("%d%d",&pos1,&pos2); else scanf("%d%d%d",&pos,&m,&plus);
if (c=='R') printf("%lld\n",sum(pos2)-sum(pos1-1)); else
for (i=1; i<=50; i++)
{
back=pos;
while (pos<=1000000)
{
    update(pos,m);
    pos+=lowbit(pos);
}
pos-=1000000;
while (pos<=1000000)
{
    update(pos,m);
    pos+=lowbit(pos);
}
pos-=1000000;
while (pos<=1000000)
{
    update(pos,998*m);
    pos+=lowbit(pos);
}
pos=back+plus;
if (pos>1000000) pos-=1000000;
}
}
}