Jaggu Playing with Balloons
Problem Statement :
Jaggu is a little kid and he likes playing with water balloons. He took 1 million ( 106 ) empty buckets and he filled the bucket with water balloons under the instruction of his sister Ishika.
His sister gives him two types of commands:
R pos1 pos2 which implies that jaggu needs to tell her what is the total number of water balloons in the bucket from pos1 to pos2 (both included).
U pos M plus which implies that he has to work like the function
Update(pos,M,plus)
void Update(int pos,int M,int plus)
{
int N=1000000; //1 million
for (int i=1;i<=50;i++)
{
int back = pos
for(int j=1;j<=1000;j++)
{
add M water ballons at bucket pos
int s,in=__builtin_popcount(pos);
for(int k=0;;k++)
{
s=pos+pow(2,k)
if( __builtin_popcount(s) <= in )
{
in = __builtin_popcount(s)
pos = s;
if(pos>N) break;
add M water ballons at bucket pos
}
}
pos = pos - N
}
pos = back+plus;
if(pos>N) pos-=N;
}
}
Jaggu is too lazy to put the water ballons in the bucket. Afraid that he might be caught for not doing what his sister told him to do so, he asks your help to provide correct answers for each of his sister's query. .
Input Format
First line contains Q, number of queries to follow.
Next Q line follows , which can be either an Update Query or Report Query.Each Update Query is followed by atleast 1 report query.
Output Format
For each report query , output the answer in a separate line.
Constraints
1 ≤ Q ≤ 2 * 105
1 ≤ pos1,pos2,pos ≤ 106
pos1 ≤ pos2
1 ≤ M ≤ 10
1 ≤ plus ≤ 999999
Solution :
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;
}
}
}
View More Similar Problems
Sparse Arrays
There is a collection of input strings and a collection of query strings. For each query string, determine how many times it occurs in the list of input strings. Return an array of the results. Example: strings=['ab', 'ab', 'abc'] queries=['ab', 'abc', 'bc'] There are instances of 'ab', 1 of 'abc' and 0 of 'bc'. For each query, add an element to the return array, results=[2,1,0]. Fun
View Solution →Array Manipulation
Starting with a 1-indexed array of zeros and a list of operations, for each operation add a value to each of the array element between two given indices, inclusive. Once all operations have been performed, return the maximum value in the array. Example: n=10 queries=[[1,5,3], [4,8,7], [6,9,1]] Queries are interpreted as follows: a b k 1 5 3 4 8 7 6 9 1 Add the valu
View Solution →Print the Elements of a Linked List
This is an to practice traversing a linked list. Given a pointer to the head node of a linked list, print each node's data element, one per line. If the head pointer is null (indicating the list is empty), there is nothing to print. Function Description: Complete the printLinkedList function in the editor below. printLinkedList has the following parameter(s): 1.SinglyLinkedListNode
View Solution →Insert a Node at the Tail of a Linked List
You are given the pointer to the head node of a linked list and an integer to add to the list. Create a new node with the given integer. Insert this node at the tail of the linked list and return the head node of the linked list formed after inserting this new node. The given head pointer may be null, meaning that the initial list is empty. Input Format: You have to complete the SinglyLink
View Solution →Insert a Node at the head of a Linked List
Given a pointer to the head of a linked list, insert a new node before the head. The next value in the new node should point to head and the data value should be replaced with a given value. Return a reference to the new head of the list. The head pointer given may be null meaning that the initial list is empty. Function Description: Complete the function insertNodeAtHead in the editor below
View Solution →Insert a node at a specific position in a linked list
Given the pointer to the head node of a linked list and an integer to insert at a certain position, create a new node with the given integer as its data attribute, insert this node at the desired position and return the head node. A position of 0 indicates head, a position of 1 indicates one node away from the head and so on. The head pointer given may be null meaning that the initial list is e
View Solution →