SHARE
TWEET

google kickstart Street Checkers

a guest Aug 25th, 2019 27 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <chrono>
  7. #include <complex>
  8. #define endl "\n"
  9. #define ll long long int
  10. #define vi vector<int>
  11. #define vll vector<ll>
  12. #define vvi vector < vi >
  13. #define pii pair<int,int>
  14. #define pll pair<long long, long long>
  15. #define mod 1000000007
  16. #define inf 1000000000000000001;
  17. #define all(c) c.begin(),c.end()
  18. #define mp(x,y) make_pair(x,y)
  19. #define mem(a,val) memset(a,val,sizeof(a))
  20. #define eb emplace_back
  21. #define f first
  22. #define s second
  23. using namespace std;
  24.  
  25.  
  26. int main()
  27. {
  28.     int T;
  29.     cin>>T;
  30.     for(int t=1;t<=T;t++)
  31.     {
  32.  
  33.         ll l,r;
  34.  
  35.         cin>>l>>r;
  36.  
  37.         vi odd(r-l+1,0),even(r-l+1,0);
  38.  
  39.         int iter = floor(sqrt(r));
  40.  
  41.         for(int i=1; i<=iter; i++){
  42.             if(i%2==0){
  43.                 int shift = l%i;
  44.  
  45.                 for(int j=(shift)?(l+i-shift):l; j<=r; j+=i){
  46.                     if(i>floor(sqrt(j))) continue;
  47.                     even[j-l]++;
  48.                     if(i*i==j) continue;
  49.                     if((j/i)%2==1) odd[j-l]++;
  50.                     else even[j-l]++;
  51.                 }
  52.             } else{
  53.                 int shift = l%i;
  54.  
  55.                 for(int j=(shift)?(l+i-shift):l; j<=r; j+=i){
  56.                     if(i>floor(sqrt(j))) continue;
  57.                     odd[j-l]++;
  58.                     if(i*i==j) continue;
  59.                     if((j/i)%2==1) odd[j-l]++;
  60.                     else even[j-l]++;
  61.                 }
  62.             }
  63.         }
  64.  
  65.         ll ans = 0;
  66.  
  67.         for(int i=0; i<r-l+1; i++){
  68.             if(abs(odd[i]-even[i])<=2) ans++;
  69.         }
  70.  
  71.         // for(auto i : odd) cout<<i<<" ";
  72.         // cout<<"\n";
  73.         //
  74.         // for(auto i : even) cout<<i<<" ";
  75.         // cout<<"\n";
  76.         cout<<"Case #"<<t<<": "<<ans<<endl;
  77.     }
  78.     return 0;
  79. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top