2.1 years ago

SS • 0

New Delhi

Solution for Beauty of an array problem 

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define endl "\n"

const ll mod  = 1e9+7;
const ld eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf  = 1e15 ;
const ll minf = -inf ;

int f(vector<int>& a, int y, int x){
    int ans = x;
    for(int i = 31; i>=0; i--){
        if(ans>>i&1) continue;
        vector<int> temp;
        int c = 0;
        for(int j = 0; j<a.size(); j++){
            if(a[j]>>i&1){
                c++;
                temp.push_back(a[j]);
            }
        }
        if(c>=y){
            ans |= (1<<i);
            a = temp;
        }
    }
    return ans;
}

void test(){

    // O(m*n) time m<=1e3 hence n<=1e5 to pass
    int n, m; cin>>n>>m;
    vector<int> arr(n, 0);
    vector<int> pre(n, 0);

    for(int i = 0; i<n; i++){
        cin>>arr[i];
        if(i == 0) pre[i] = arr[i];
        else pre[i] = pre[i-1]+arr[i];
    }

    while(m--){
        // O(32*n) per query
        int k, y, x; cin>>k>>y>>x;

        vector<int> a;
        a.push_back(pre[k-1]);
        for(int i = k; i<n; i++){
            a.push_back(pre[i]-pre[i-k]);
        }
        cout<<f(a, y, x)<<endl;
    }

    
    return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    // int t; cin>>t;

    while(t--){
        test();
    }
    
    return 0;
}