fork download
copy 
  1. namespace CodeJam.Sample.DataStructures
  2. {
  3.     using System;
  4.     using System.Collections.Generic;
  5.     using System.Linq;
  6.  
  7.     /// <summary>
  8.     /// Implement the Binary Indexed Tree data structure. 
  9.     /// Simulation of an array of N elements for which the operation of incrementing x[i] by j 
  10.     /// and the operation give x[1]+...+x[i] are both O(log N).
  11.     /// </summary>
  12.     public class BinaryIndexedTree
  13.     {
  14.         /// <summary>
  15.         /// The number of elements in the array we are simulating.
  16.         /// </summary>
  17.         private int numberOfElements;
  18.  
  19.         /// <summary>
  20.         /// The contents of the internal array.
  21.         /// </summary>
  22.         private int[] contents;
  23.  
  24.         /// <summary>
  25.         /// Initializes a new instance of the <see cref="CodeJam.Sample.DataStructures.BinaryIndexedTree"/> class.
  26.         /// </summary>
  27.         /// <param name="n">Number of elements in the array.</param>
  28.         public BinaryIndexedTree(int n)
  29.         {
  30.             this.numberOfElements = n;
  31.             this.contents = new int[n + 1];
  32.         }
  33.  
  34.         /// <summary>
  35.         /// Gets or sets the element at the specified index in the array.
  36.         /// </summary>
  37.         /// <returns>The element at the index.</returns>
  38.         /// <param name="index">1-Based Index at which to get or set.</param>
  39.         public int this[int index]
  40.         {
  41.             get { return this.Accumulate(index) - this.Accumulate(index - 1); }
  42.             set { this.Increment(index, value - this[index]); }
  43.         }
  44.  
  45.         /// <summary>
  46.         /// Increment an element of the simulated array by a certain amount.
  47.         /// </summary>
  48.         /// <param name="index">1-Based index of simulated array.</param>
  49.         /// <param name="amount">Amount by which to increment.</param>
  50.         public void Increment(int index, int amount)
  51.         {
  52.             while (index <= this.numberOfElements)
  53.             {
  54.                 this.contents[index] += amount;
  55.                 index += this.LeastSignificantBit(index);
  56.             }
  57.         }
  58.  
  59.         /// <summary>
  60.         /// Return the sum of all of the elements in the array up to and including the given index
  61.         /// </summary>
  62.         /// <returns>The sum of all elements up to the given index</returns>
  63.         /// <param name="index">1-Based index up to which to accumulate.</param>
  64.         public int Accumulate(int index)
  65.         {
  66.             int accumulation = 0;
  67.             while (index > 0) 
  68.             {
  69.                 accumulation += this.contents[index];
  70.                 index -= this.LeastSignificantBit(index);
  71.             }
  72.  
  73.             return accumulation;
  74.         }
  75.  
  76.         /// <summary>
  77.         /// Returns the least significant bit of an integer.
  78.         /// </summary>
  79.         /// <returns>The least significant bit.</returns>
  80.         /// <param name="n">Input integer.</param>
  81.         private int LeastSignificantBit(int n)
  82.         {
  83.             return n & (-n);
  84.         }
  85.     }
  86.  
  87.     /// <summary>
  88.     /// A test class for running on ideone
  89.     /// </summary>
  90.     public class Test
  91.     {
  92.         /// <summary>
  93.         /// Solve the problem, using the Binary Indexed Tree data structure.
  94.         /// </summary>
  95.         public static void Main()
  96.         {
  97.             int numberOfCases = GetInt();
  98.             for (int caseIndex = 1; caseIndex <= numberOfCases; ++caseIndex)
  99.             {
  100.                 var parameters = GetInts();
  101.                 int numberOfStudents = parameters[0];
  102.                 int numberOfChocolates = parameters[1];
  103.  
  104.                 /* We are going to use a BinaryIndexedTree to simulate an array x[1], ..., x[N]
  105.                  * where student i has x[1]+...+x[i] chocolates.
  106.                  * 
  107.                  * Then we can find out how many chocolates student i has by calling Accumulate(i) (O(log N) time)
  108.                  * and we can give K chocolates to students i, i+1, ..., j by calling:
  109.                  *  Increment(i, K)
  110.                  *  Increment(j+1, -K)
  111.                  * 
  112.                  * Note our BinaryIndexedTree uses 1-indexed indices, and the problem uses 0-indexed indices, so we will have to
  113.                  * add 1 to the student indices we get.
  114.                  */
  115.                 var bit = new BinaryIndexedTree(numberOfStudents);
  116.                 for (int chocolateIndex = 0; chocolateIndex < numberOfChocolates; ++chocolateIndex)
  117.                 {
  118.                     parameters = GetInts();
  119.                     int fromStudent = parameters[0];
  120.                     int toStudent = parameters[1];
  121.                     int chocolateGift = parameters[2];
  122.                     bit.Increment(fromStudent + 1, chocolateGift);
  123.                     bit.Increment(toStudent + 2, -chocolateGift);
  124.                 }
  125.  
  126.                 int numberOfFriends = GetInt();
  127.                 for (int friendIndex = 0; friendIndex < numberOfFriends; ++friendIndex)
  128.                 {
  129.                     int friendLocation = GetInt();
  130.                     Console.WriteLine(bit.Accumulate(friendLocation + 1));
  131.                 }
  132.             }
  133.         }
  134.  
  135.         /// <summary>
  136.         /// Read a single integer from stdin
  137.         /// </summary>
  138.         /// <returns>The read integer.</returns>
  139.         private static int GetInt()
  140.         {
  141.             return int.Parse(Console.ReadLine());
  142.         }
  143.  
  144.         /// <summary>
  145.         /// Read a line of space separated integers from stdin
  146.         /// </summary>
  147.         /// <returns>The read integers.</returns>
  148.         private static List<int> GetInts()
  149.         {
  150.             return Console.ReadLine().Split(' ').Select(_ => int.Parse(_)).ToList();
  151.         }
  152.     }
  153. }
Success #stdin #stdout 0.04s 24264KB
comments (?)
stdin
copy 
1
6 4
3 5 2
2 4 3
1 5 1
0 2 4
4
4
3
2
0
stdout
copy 
6
6
8
4
https://ideone.com/Ammsll
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!