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 \leq b \leq 30} cnt_b$$$, where $$$cnt_b$$$ 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.

616733C - Karen and Coffee

There are two separate tasks here:

Efficiently generate an array $$$c$$$ where $$$c_i$$$ is the number of recipes that recommend temperature $$$i$$$.

Efficiently answer queries "how many numbers $$$c_a, c_{a+1}, c_{a+2}, \dots, c_{b}$$$" are at least $$$k$$$?" where $$$k$$$ is fixed across all queries.

There are some solutions to this task using advanced data structures or algorithms. For example, a conceptually straightforward idea is the following: create a segment tree $$$c$$$. We can treat all recipes as range update queries which we can do efficiently in $$$O(nlogm)$$$ (where $$$m$$$ is the largest $$$a_i$$$ or $$$b_i$$$) time using lazy propagation.

After all recipes, we replace all $$$c_i$$$ by $$$1$$$ if it's at least $$$k$$$, and $$$0$$$ otherwise. Afterwards, each of the next $$$q$$$ queries is a basic range sum query, which can be done simply in $$$O(qlogm)$$$ time.

Other solutions exist, too: Fenwick trees with range updates, event sorting, sqrt-decomposition with binary search, Mo's algorithm, and so on. These solutions all pass, but they are all overkill for this task.

A very simple solution is as follows. Initialize $$$c$$$ with all zeroes. For recipe that recommends temperatures between $$$l_i$$$ and $$$r_i$$$, we should increment $$$c_{l_i}$$$ and decrement $$$c_{r_{i+1}}$$$.

Cumulate all values. That is, set $$$c_i$$$ to $$$c_1 + c_2 + c_3 + \dots + c_i$$$. This can be done with one pass through the array.

Now, magically, $$$c_i$$$ is now the number of recipes that recommend temperature $$$i$$$. If $$$c_i$$$ is at least $$$k$$$, set it to $$$1$$$, otherwise, set it to $$$0$$$.

Cumulate all values again.

Now, every query that asks for the number of admissible temperatures between $$$a$$$ and $$$b$$$ can be answered simply as $$$c_b - c_a - 1$$$.

This runs in $$$O(n+q+m)$$$, which is really fast.