fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. #define ina(a) for(auto &i: a) cin>>i
  6. #define opa(a) for(auto &i: a) cout << i << ' '; cout << endl;
  7. #define swap(a, i, j) { auto temp = a[i]; a[i] = a[j]; a[j] = temp; }
  8. #define v vector
  9. #define p(res) cout << res << '\n'
  10.  
  11. int f(v<v<int>> &dp, int mid, int l){
  12.     int res=0;
  13.     for(int b=0; b<32; b++){
  14.         int left=(l>0)?dp[b][l-1]:0;
  15.         if (dp[b][mid]-left == l-mid+1) res|=(1<<b);
  16.     }
  17.     return res;
  18. }
  19.  
  20. // Code Here!
  21. void solve(){
  22.     int n, q; cin>>n>>q;
  23.     v<int> a(n); 
  24.     ina(a);
  25.     int res=0;
  26.     v<v<int>> dp(32, v<int> (n, 0));
  27.     for(int i=0; i<n; i++){
  28.         for(int b=0; b<32; b++){
  29.             if (a[i]&(1<<b)) dp[b][i]++;
  30.         }
  31.     }
  32.     for(int b=0; b<32; b++){
  33.         for(int i=1; i<n; i++){
  34.             dp[b][i]+=dp[b][i-1];
  35.         }
  36.     }
  37.     for(int qq=0; qq<q; qq++){
  38.         int k, l; cin>>k>>l; l--;
  39.         int i=l, j=n, cur=n+1; 
  40.         while(i<=j){
  41.             int mid=i+(j-i)/2;
  42.             if (f(dp, mid, l) >= k) {
  43.                 cur=mid; i=mid+1;
  44.             }
  45.             else j=mid-1;
  46.         }
  47.         if (cur!=n+1) cur++;
  48.         res^=cur;
  49.     }
  50.     p(res);
  51. }
  52.  
  53. int main(){
  54.     int t=1;
  55.     cin>>t;
  56.     while(t--){
  57.         solve();
  58.     }
  59. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
1
16 10
20 1 4 9 4 2 6 11 2 4 23 23 8 20 20 13
18 2
9 10
30 12
18 16
15 8
30 11
22 3
27 4
22 6
21 10
11 3
stdout
copy 
0
https://ideone.com/AcB05L
language:
C++14 (gcc 8.3)
created:
1 day 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!