fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define bit(mask, i) (((mask) >> (i)) & 1)
  6.  
  7. using namespace std;
  8.  
  9. const int max_pos = 35;
  10.  
  11. int q;
  12. ll a, dp[max_pos + 10];
  13.  
  14. ll recur(ll n, int pos, ll num = 0, bool free = 0)
  15. {
  16.     if (pos == -1)
  17.         return 1;
  18.     if (free && dp[pos] != -1)
  19.         return dp[pos];
  20.     ll ans = 0;
  21.     int limit = free ? 1 : bit(n, pos);
  22.     if (bit(a, pos))
  23.     {
  24.         if (limit)
  25.             ans += recur(n, pos - 1, num * 2 + 1, free);
  26.     }
  27.     else
  28.     {
  29.         for (int digit = 0; digit <= limit; digit++)
  30.             ans += recur(n, pos - 1, num * 2 + digit, free || digit < limit);
  31.     }
  32.     if (free)
  33.         dp[pos] = ans;
  34.     return ans;
  35. }
  36. ll f(ll n)
  37. {
  38.     memset(dp, -1, sizeof dp);
  39.     return recur(n, max_pos);
  40. }
  41.  
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  45.     if (fopen("OR.INP", "r"))
  46.     {
  47.         freopen("OR.INP", "r", stdin);
  48.         freopen("OR.OUT", "w", stdout);
  49.     }
  50.  
  51.     cin >> q;
  52.     while (q--)
  53.     {
  54.         ll l, r;
  55.         cin >> a >> l >> r;
  56.         cout << f(r) - f(l - 1), el;
  57.     }
  58. }
  59.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vCE6t1
language:
C++14 (gcc 8.3)
created:
9 hours 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!