HackerEarth Triangular Ranges problem solution

In this HackerEarth Triangular Ranges problem solution, Kuku recently learnt about triangular numbers. If you are not familiar with the triangular numbers follow this link first http://en.wikipedia.org/wiki/Triangular_number. Ani thinks Kuku has not learnt it properly and start asking questions. But, As we all know kuku is one of the most intelligent on this planet. He answered each and every question correctly. This annoyed Ani and he geared up his question’s level and started asking even harder questions. Kuku can’t answer such big questions manually. So , He decided to write a computer program which can answer Ani’s questions .

Kuku is good at mathematics but not at programming ( Dont Doubt His Intelligence ) . So,he hired you ( A World Class Programmer ) to write a computer program which can answer Ani’s Questions with in time.

In Each question, Ani has given a range [L,R] and asked kuku to calculate numbers of such triplets [A,B,K] which follows

A + B = K

where A, B are any two triangular numbers and K must be in an integers that belongs to given range [L,R] both inclusive.

HackerEarth Triangular Ranges problem solution.

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<climits>
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long
#define VI vector<int>
#define PII pair<int,int>
#define VII vector<PII >
#define ft first
#define sd second
#define rz(v,n) v.resize(n)
#define VL vector<ll>
#define VLL vector<pair<ll,ll> >
#define PLL pair< ll,ll >
#define all(v) v.begin(),v.end()
#define IT iterator
// Input/Output
#define print(v) printf("%dn",v)
#define printll(v) printf("%lldn",v)
#define scan(v) scanf("%d",&v)
#define scanll(v) scanf("%lld",&v)
// loops
#define FOR(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) for(i=0;i<n;i++)
//extra
#define ms(v,val) memset(v,val,sizeof(v))
#define fill(v,val) fill(all(v),val)
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define PIE 3.14159265358979323846264338327950
#define MOD 1000000007
#ifdef ONLINE_JUDGE
 inline void inp( int &n )
 {
    n=0;
    int ch=getchar_unlocked();int sign=1;
    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}

    while(  ch >= '0' && ch <= '9' )
            n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
    n=n*sign;
  }
#else
inline void inp(int &n){
 cin>>n;
}
#endif
ll UpperLimit=1000000000000LL;
#define MAX 1414215
ll A[MAX],size;
inline ll pre_process(){
 size=1;
 while(((size*(size+1))/2)<=UpperLimit){
  A[size]=(size*(size+1))/2;
  size++;
 }
 --size;
 cout<<size<<endl;
}
// UpperBound
inline int mylower_bound(int L,int R,ll val){
   int left=L;
   int right=R;
   if(A[right]<val) return 0;
   if(A[left]>=val) return (R-L+1);
   while(L<=R){
     int mid=(L+R)/2;
     if(A[mid]>=val&&(mid==left||A[mid-1]<val))
      return (right-mid+1);
     if(A[mid]>=val) R=mid-1;
     else L=mid+1;
   }
}
// LowerBound
inline int myupper_bound(int L,int R,ll val){
   int left=L;
   int right=R,mid;
   if(A[left]>val) return (R-L+1);
   if(A[right]<=val) return 0;
   while(L<=R){
     mid=(L+R)/2;
     if(A[mid]>val&&(mid==left||A[mid-1]<=val))
      return (right-mid+1);
     else if(A[mid]>val) R=mid-1;
     else L=mid+1;
   }
}
inline ll cal(ll L,ll R){
  ll count=0;
  for(int i=1;i<=size&&A[i]<R;i++){
   count+=(mylower_bound(i,size,L-A[i])-myupper_bound(i,size,R-A[i]));
  }
  return count;
}

int main(){
  pre_process();
  int t;
  inp(t);
  assert(t<=5);
  while(t--){
   ll L,R;
   scanll(L);scanll(R);
   assert(L<=R&&L<=UpperLimit&&R<=UpperLimit);
   printll(cal(L,R));
 }
 return 0;
}

Second solution

#include <iostream>
    #include <algorithm>
    #include <cmath>
    #include <cassert>
    using namespace std;
    int Size=0;
    long long int tri_num[2000005];
    void pre_cal()
    {
        long long int i;
        for(i=1;;i++){
            tri_num[i-1]=(i*(i+1))/2;
            if(tri_num[i-1]>1000000000000LL)
                break;
        }
        Size=i;
    }
    int UpperBound(int i,long long val)
    {
        int lb=i,ub=Size-1,mid;
        while(lb<ub)
        {
            mid=(lb+ub)/2;
            if(tri_num[mid]>val)
                ub=mid;
            else
                lb=mid+1;
        }   
        return ub;
    }
    int LowerBound(int i,long long val)
    {
        int lb=i,ub=Size-1,mid;
        while(lb<ub)
        {
            mid=(lb+ub)/2;
            if(tri_num[mid]<val)
                lb=mid+1;
            else
                ub=mid;
        }
        return lb;
    }
    int main()
    {
        pre_cal();
        int test,i;
        cin>>test;
        while(test--)
        {
            long long int L,R,Count=0;
            cin>>L>>R;
            assert(L<=R && L>=1 && L<=1000000000000LL && R>=1 && R<=1000000000000LL );
            for(i=0;i<Size && tri_num[i]<R;i++)
                Count=Count+(UpperBound(i,R-tri_num[i])-LowerBound(i,L-tri_num[i]));
            cout<<Count<<endl;
        
        }
        return 0;
    }

coding problems solutions