616733A - Promo

First of all, there is an answer with exactly $$$x$$$ items bought. Suppose items worth $$$p_1 \leq p_2≤ \dots \leq p_m$$$ ($$$x \lt m$$$) were purchased. Then by removing $$$p_1$$$ from this set, the sum of $$$y$$$ the cheapest items in the set will change by $$$p_{y+1}−p_1 \geq 0$$$, which means the answer will not decrease.

The second fact that is necessary to solve the problem — $$$x$$$ of the most expensive items should be chosen. Otherwise, one can remove the minimum price item from the set and add an item with a higher price (it can always be found), which means the answer will not decrease.

Using these two facts, it is enough to sort the array and use prefix sums.

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

int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<long long> p(n), s(n + 1);
  for (auto& x : p) cin >> x;

  sort(p.begin(), p.end());

  for (int i = 0; i < n; ++i) s[i + 1] = s[i] + p[I];

  while (q--) {
    int x, y;
    cin >> x >> y;
    cout << s[n - x + y] - s[n - x] << '\n';
  }
} 

616733B - And It's Non-Zero

Let's solve the complement problem: find the largest subsequence of the array such that their bitwise AND is non-zero. Let $$$x$$$ be the bitwise and of the optimal subsequence. Since $$$x \neq 0$$$, at least one bit must be set in $$$x$$$. Let's iterate over that bit, call it $$$b$$$, and in each iteration, calculate the largest subsequence whose bitwise and has that bit set. For the $$$b$$$-th bit to be set in the final answer, every element in the chosen subsequence must have that bit set. Since choosing every element with the $$$b$$$-th bit on is a valid subsequence, this implies that the answer for the $$$b$$$-th bit is the number of elements that have the $$$b$$$-th bit set. Thus, the answer to the final problem is $$$n - max_{1≤b≤30} cnt_b$$$, where cntb is the number of elements who have the $$$b$$$-th bit set.

Note: it doesn't matter if the final answer contains more than one set bit, it's still covered in at least one of the cases, and the bitwise and will still be non-zero.

All that remains is counting the number of elements in the range $$$[l \dots r]$$$ with the $$$b$$$-th bit set, for all $$$b$$$. This can be done with precomputation, by creating $$$b$$$ prefix sum arrays before answering any of the test cases, where the $$$i$$$-th element of the $$$b$$$-th array is the number of integers $$$\leq i$$$ that have the $$$b$$$-th bit on. After this, you can use the prefix sum technique to answer queries, as $$$cnt_b=a_{b,r}−a_{b,l}$$$, if $$$a_b$$$ is the $$$b$$$-th array.