Advertisement
PikMike

Untitled

Jun 10th, 2016
359
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define pb push_back
  4. #define mp make_pair
  5. #define sz size
  6. #define ll long long
  7. #define ld long double
  8. #define fs first
  9. #define sc second
  10. #define forn(i, f, t) for(int i = f; i < t; i++)
  11. #define all(x) (x).begin(), (x).end()
  12. #define ins insert
  13.  
  14. const int INF = 2147483647;
  15. const int MOD = 1000000007;
  16. const ll INF64 = 9223372036854775807;
  17. const ld EPS = 1e-7;
  18.  
  19. using namespace std;
  20.  
  21.  
  22. int main(){
  23.     int l, r;
  24.     scanf("%d%d", &l, &r);
  25.     int n = r - l + 1;
  26.  
  27.     r++;
  28.  
  29.     int k = 0, cntl[31];
  30.     while ((1 << k) <= l) k++; k--;
  31.     forn(i, 0, 31) cntl[i] = 0;
  32.     vector<int> posl;
  33.     while (l){
  34.         if (l & (1 << k)){
  35.             forn(i, 0, k) cntl[i] += (1 << (k - 1));
  36.             forn(i, 0, posl.sz()) cntl[posl[i]] += (1 << k);
  37.             posl.pb(k);
  38.             l ^= (1 << k);
  39.         }
  40.         k--;
  41.     }
  42.     // forn(i, 0, 16) printf("%d ", cntl[i]); printf("\n");
  43.  
  44.     k = 0;
  45.     int cntr[31];
  46.     while ((1 << k) <= r) k++; k--;
  47.     forn(i, 0, 31) cntr[i] = 0;
  48.     vector<int> posr;
  49.     while (r){
  50.         if (r & (1 << k)){
  51.             forn(i, 0, k) cntr[i] += (1 << (k - 1));
  52.             forn(i, 0, posr.sz()) cntr[posr[i]] += (1 << k);
  53.             posr.pb(k);
  54.             r ^= (1 << k);
  55.         }
  56.         k--;
  57.     }
  58.     // forn(i, 0, 16) printf("%d ", cntr[i]); printf("\n");
  59.  
  60.     int cnt[31];
  61.     forn(i, 0, 31)
  62.         cnt[i] = cntr[i] - cntl[i];
  63.     // forn(i, 0, 16) printf("%d ", cnt[i]); printf("\n");
  64.     ll ans = 0ll;
  65.     forn(i, 0, 31) if (cnt[i] * 2 > n) ans += (1 << i);
  66.     cout << ans << "\n";
  67.     return 0;
  68. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement