pratiyush7

Untitled

Dec 4th, 2021
693
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. const int maxn = 1e5 + 14, lg = 30;
  6. int n;
  7. ll cnt[maxn][lg];
  8. int main(){
  9.     ios::sync_with_stdio(0), cin.tie(0);
  10.     cin >> n;
  11.     for(int i = 0; i < n; i++){
  12.         int x;
  13.         cin >> x;
  14.         for(int j = 0; j < lg; j++)
  15.             cnt[i + 1][j] = cnt[i][j] + max(0, (1 << j) - (x & (1 << j + 1) - 1));
  16.     }
  17.     int q;
  18.     cin >> q;
  19.     while(q--){
  20.         int l, r;
  21.         cin >> l >> r;
  22.         l--;
  23.         ll ans = LLONG_MAX;
  24.         for(int i = 0; i < lg; i++)
  25.             ans = min(ans, cnt[r][i] - cnt[l][i]);
  26.         cout << ans << '\n';
  27.     }
  28. }
RAW Paste Data