[Codeforces] F. Daniel and Spring Cleaning

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : F. Daniel and Spring Cleaning
Source            : Codeforces
Category          : Dynamic Programing
Algorithm         : Digit DP, A-B
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
long long dp[32][2][2][2][2];  
bool memoize[32][2][2][2][2];  
string a;  
string b;  
  
long long solve(int pos, bool small1, bool large1, bool small2, bool large2)  
{  
      if (pos < 0) return 1;  
      long long &ret = dp[pos][small1][large1][small2][large2];  
      bool &mem = memoize[pos][small1][large1][small2][large2];  
      if (mem) return ret;  
      mem = 1;  
      long long sum = 0;  
      int numa = a[pos] - '0';  
      int numb = b[pos] - '0';  
      for (int i = 0; i <= 1; i++)  
      {  
            if (small1 == 0 and i > numb) continue;  
            if (large1 == 0 and i < numa) continue;  
            for (int j = 0; j <= 1; j++)  
            {  
                  if (small2 == 0 and j > numb) continue;  
                  if (large2 == 0 and j < numa) continue;  
                  if (i & j) continue;  
                  bool nsmall1 = small1 | (i < numb);  
                  bool nlarge1 = large1 | (i > numa);  
                  bool nsmall2 = small2 | (j < numb);  
                  bool nlarge2 = large2 | (j > numa);  
                  sum += solve(pos - 1, nsmall1, nlarge1, nsmall2, nlarge2);  
            }  
      }  
      return ret = sum;  
}  
  
long long digit_dp(int l, int r)  
{  
      a.clear();  
      b.clear();  
      for (int i = 0; i < 31; i++)  
      {  
            a.push_back((l % 2) + '0');  
            b.push_back((r % 2) + '0');  
            l /= 2;  
            r /= 2;  
      }  
      memset(memoize, 0, sizeof memoize);  
      return solve(30, 0, 0, 0, 0);  
}  
  
signed main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      while (tc--)  
      {  
            int l, r;  
            cin >> l >> r;  
            cout << digit_dp(l, r) << '\n';  
      }  
}