fork download 
  1. #define _GLIBCXX_FILESYSTEM
  2. #include <bits/stdc++.h>
  3. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  4. #define int long long
  5. #define F first
  6. #define S second
  7. using namespace std;
  8.  
  9. int l,r,ii,k;
  10. vector<int> lower(60);  // binary represnation of L
  11. vector<int> upper(60);   // binary represnation of R
  12. vector<int> kt(60,-1);  // binary represnation of k % 2^i
  13. int dp[60][2][2][2];
  14. int cache[60][2][2][2];
  15. int solve(int ix,int freeup,int freedn,int freek)
  16. {
  17.     if(ix==-1)
  18.     {
  19.         if(freek)return 1;
  20.         else return 0;
  21.     }
  22.     if(dp[ix][freeup][freedn][freek]!=-1) return dp[ix][freeup][freedn][freek];
  23.  
  24.     int ans=0;
  25.     int tmp=0;
  26.  
  27.     if(freedn || (lower[ix]==0) )
  28.     {
  29.         ans+=solve(ix-1,freeup|(upper[ix]==1),freedn,freek| (kt[ix]!=-1 &&kt[ix]!=0));
  30.  
  31.     }
  32.     if(freeup || (upper[ix]==1) )
  33.     {
  34.         tmp=solve(ix-1,freeup,freedn|(lower[ix]==0),freek|(kt[ix]!=-1&& kt[ix]!=1));
  35.  
  36.         // tmp is the (number of numbers) that have this current digit ==1 but only starting from this index till the 0th index
  37.  
  38.     }
  39.     ans+=tmp;
  40.     return dp[ix][freeup][freedn][freek]=ans;
  41. }
  42. signed main()
  43. {
  44.     IOS
  45.     int t;
  46.     cin>>t;
  47.     while(t--)
  48.     {
  49.         memset(dp,-1,sizeof(dp));
  50.         memset(dig,0,sizeof(dig));
  51.         for(int i=0; i<60; i++)
  52.         {
  53.             digis[i]=0;
  54.             upper[i]=0;
  55.             lower[i]=0;
  56.             kt[i]=-1;
  57.         }
  58.         cin>>l>>r>>ii>>k;
  59.         int i=__builtin_clzll(l);
  60.  
  61.         for(i=63-i; i>=0; i--)
  62.         {
  63.             if(l & (1ll<<i))
  64.             {
  65.                 lower[i]=1;
  66.             }
  67.         }
  68.         i=__builtin_clzll(r);
  69.         for(i=63-i; i>=0; i--)
  70.         {
  71.             if(r & (1ll<<i))
  72.             {
  73.                 upper[i]=1;
  74.             }
  75.         }
  76.         for(int c=0; c<ii; c++)
  77.         {
  78.             if(k&(1ll<<c))
  79.                 kt[c]=1;
  80.             else kt[c]=0;
  81.         }
  82.         int ans=0;
  83.         solve(59,0,0,0);
  84.  
  85.         // cout<<ans<<"\n";
  86.     }
  87.  
  88. }
  89.  
  90.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main()’:
prog.cpp:51:16: error: ‘dig’ was not declared in this scope
         memset(dig,0,sizeof(dig));
                ^~~
prog.cpp:51:16: note: suggested alternative: ‘div’
         memset(dig,0,sizeof(dig));
                ^~~
                div
stdout 
Standard output is empty
https://ideone.com/YYmSO6
language:
C++14 (gcc 8.3)
created:
6 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!