Handling addition of two binary numbers This code is for handling addition of two binary numbers, which can be as long as 100,000 bits... and up to 500,000 queries are performed.

High-level pseudocode:


First input N: number of bits in binary number A and B.
Second input Q: number of queries to be performed.
Next N inputs: 0/1s ... bits for A
Next N inputs: 0/1s ... bits for B
Next Q inputs are one of the following:


set_a INDEX VALUE: as a result I set a[INDEX] = VALUE
set_b INDEX VALUE: as a result I set b[INDEX] = VALUE
get_c INDEX: as a result I print c[INDEX] where C = A+B (binary addition, like 100 + 101 = 1001)





#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;set&gt;
#include &lt;algorithm&gt;
#include &lt;utility&gt;  // For pair
#include &lt;iterator&gt; // For iterator, bidirectional_iterator_tag, reverse_iterator
#include &lt;climits&gt;  // For CHAR_BIT, ULONG_MAX
using namespace std;


class VanEmdeBoasTree {};

int main(int argc, char * argv[])
{
  int n, q;
  char c;
  bool a[100005] = {0}, b[100005] = {0};
  VanEmdeBoasTree equals;
  cin&gt;&gt;n;
  cin&gt;&gt;q;

  for(int i=0;i&lt;n;i++){
    cin&gt;&gt;c;
    if(c=='1')
      a[n-i-1] = true;
  }
  for(int i=0;i&lt;n;i++){
    cin&gt;&gt;c;
    if(c=='1')
      b[n-i-1] = true;
    if(a[n-i-1] == b[n-i-1]){
      equals.insert(n-i-1);
    }
  }

  string query;
  int index, val, lastval;
  for(int i=0;i&lt;q;i++){
    cin&gt;&gt;query;
    cin&gt;&gt;index;
    if(query[4] == 'a'){
      cin&gt;&gt;val;
      if(a[index] != val){
        a[index] = val;
        if(a[index] == b[index]){
          equals.insert(index);
        }else{
          equals.erase(index);
        }
      }
    }else if(query[4] == 'b'){
      cin&gt;&gt;val;
      if(b[index] != val){
        b[index] = val;
        if(a[index] == b[index]){
          equals.insert(index);
        }else{
          equals.erase(index);
        }
      }
    }else if(query[4] == 'c'){
      int final = 0;
      if(index == n){
        if(equals.size() &gt; 0){
          VanEmdeBoasTree::const_iterator it = equals.predecessor(index+1); 
          if(it!=equals.end() &amp;&amp; a[*it] == 1){
            final = 1;
          }
        }
      }else{
        final = (a[index] + b[index])%2;
        if(equals.size() &gt; 0){
          VanEmdeBoasTree::const_iterator it = equals.predecessor(index); 
          int last = -1;
          if(it != equals.end())
            last = *it;
          if( last!=-1 &amp;&amp; index!=0 &amp;&amp; it!=equals.end() &amp;&amp;  a[last] == 1){
            final = 1-final;
          }
        }
      }
      cout&lt;&lt;final;
    }
  }

  return 0;
}


My solution is not fast enough as the Judge says "time out" after some test cases.
Profile and you will find your bottlenecks, you can do that with gprof under gcc/g++. You have to set the -g -pg on compile and then run your program like you would do normally. It will then produce a gmon.out file which you can open with gprof main gmon.out (assuming main is the name of your executable).

It will show you, in which functions your program spends most of the time.