We decided to hold another round. It will be held from 15:30 UTC. But it is late at night in Japan, so I think clarifications won't be answered.

It's my mistake. Information on the official website is correct.

It can be seen, that you will need to use one of the top $$$O(logn)$$$ in the triplet.

How?

I had one observation: one of the triple elements is at least as big as $$$O(logn)th$$$ element on segment $$$[L, R]$$$. My guess is that we can use data structures if we fix one element of the triple. I guess that 2 elements from best triple is from top 100 elements.

There are $$$O(n)$$$ pairs $$$(a,b)$$$ which can be candidates in the answer (the same $$$O(n)$$$ for any segment).

That is because for each $$$a < k < b$$$ you should have $$$arr_k \leq arr_a$$$ and $$$arr_k \leq arr_b$$$.

So you can find these pairs with stack.

vector <pair <int, int> > e;
for (int i = 0; i < n; i++) {
  while (!st.empty() && a[st.back()] <= a[i]) {
    e.push_back({st.back(), i});
    st.pop_back();
  }
  if (!st.empty()) {
    e.push_back({st.back(), i});
  }
  st.push_back(i);
}

After that, for each query $$$(l,r)$$$ you need to find

$$$l \leq a_i \leq 2b_i - a_i \leq j \leq r$$$

with maximum $$$arr_{a_i} + arr_{b_i} + arr_{j}$$$

Let's answer these queries in offline, for that let's move $$$l$$$ from the right and maintaining the largest $$$arr_{a_i} + arr_{b_i}$$$ for fixed $$$2b_i - a_i$$$, let's call this value $$$f_{2b_i - a_i}$$$.

To answer the query at the fixed $$$l$$$ you should find $$$l \leq i \leq j \leq r$$$ with maximum possible $$$f_i + arr_j$$$.

You can do it with segment tree, maintaining the maximum possible $$$arr_i$$$, $$$f_i$$$, and $$$f_i + arr_j$$$ among all $$$tree_l \leq i \leq j \leq tree_r$$$.

data operator + (const data &a, const data &b) {
  data ret = a;
  ret.mx = max(ret.mx, max(a.mx_arr + b.mx_a, b.mx));
  ret.mx_a = max(ret.mx_a, b.mx_a);
  ret.mx_arr = max(ret.mx_arr, b.mx_arr);
  return ret;
}

sort(e.rbegin(), e.rend());
int ptr = -1;
vector <int> arr(n, -inf);
vector <vector <pair <int, int> > > qs(n);
int q;
cin >> q;
for (int i = 0; i < q; i++) {
  int l, r;
  cin >> l >> r;
  l--, r--;
  qs[l].push_back({r, i});
}
vector <int> ans(q);
vector <data> best(4 * n);
function <void(int, int, int, int, int, bool)> upd = [&] (int v, int l, int r, int i, int x, bool a) {
  if (r - l == 1) {
    if (a) {
      best[v].mx_a = max(best[v].mx_a, x);
    } else {
      best[v].mx_arr = max(best[v].mx_arr, x);
    }
    best[v].mx = max(-inf, best[v].mx_a + best[v].mx_arr);
  } else {
    int m = (l + r) / 2;
    if (i < m) {
      upd(v * 2 + 1, l, m, i, x, a);
    } else {
      upd(v * 2 + 2, m, r, i, x, a);
    }
    best[v] = best[v * 2 + 1] + best[v * 2 + 2];
  }
};
function <data(int, int, int, int, int)> get = [&] (int v, int l, int r, int tl, int tr) {
  if (tl >= r || tr <= l) {
    return data(-inf, -inf, -inf);
  } else if (tl >= l && tr <= r) {
    return best[v];
  } else {
    int tm = (tl + tr) / 2;
    return get(v * 2 + 1, l, r, tl, tm) + get(v * 2 + 2, l, r, tm, tr);
  }
};
for (int i = 0; i < n; i++) {
  upd(0, 0, n, i, a[i], true);
}
for (int l = n - 1; l >= 0; l--) {
  while (ptr + 1 < (int) e.size() && e[ptr + 1].first >= l) {
    ptr++;
    int start = e[ptr].second * 2 - e[ptr].first;
    if (start < n) {
      upd(0, 0, n, start, a[e[ptr].first] + a[e[ptr].second], false);
    }
  }
  for (auto c : qs[l]) {
    int r = c.first;
    int i = c.second;
    ans[i] = get(0, l, r + 1, 0, n).mx;
  }
}
for (int i = 0; i < q; i++) {
  cout << ans[i] << '\n';
}

I think this problem is very good. Unfortunately, haven't solved it during the contest, because I was trying to improve the idea of $$$\log$$$ maximums.

Cheers to gamegame and tmwilliamlin168 for showing me this brilliant idea of $$$O(n)$$$ pairs $$$(a,b)$$$.

Well, I solved it with some creepy BFS where you walk around for the fixed cell, and when you can understand that you are not one of the minimal guys, you should go out.

Lots of constant optimizations and $$$100$$$ points in the end.

You can do it in $$$O(RC\log (RC)).$$$

Maintain a list of components in the graph, each of which has a special cell which is infected regardless of which cell in the component is infected initially. Initially, each nonzero cell is a special cell of its own component.

Now, start a BFS from each special cell $$$A$$$ until the BFS ends or reaches a cell $$$B$$$ outside of its component. In the former case, update the answer with the number of vertices visited and mark $$$A$$$ as "dead" (represented by -1 in my solution). If $$$B$$$'s component is dead, mark $$$A$$$'s component as dead. Otherwise, merge the component of $$$A$$$ with the component of $$$B$$$. The special vertex of the union of the two components is simply the special cell of the newly visited component.

Doing the BFS from each special cell takes $$$O(RC)$$$ time. After we process all the merges, the number of components which are not dead is reduced by a factor of at least two. This can repeat at most $$$\log_2(RC)$$$ times (similar to Boruvka's algorithm).

Code

Is there a reason u choose to use Kosaraju instead of Tarjan? Also can Tarjan be used in this case? Thanks! :)

Here's my code. I just thought that traversing the array in two ways will give a correct answer.

My solution was probably a massive overkill. Suppose there are $$$c_{i}$$$ coins on house $$$i$$$ (I shall use zero based indexing). Consider the sum $$$I = \sum_{i = 0}^{n - 1} 2^{i} c_{i}$$$. This sum does not change when you send coins from house $$$i$$$ such that $$$i < n -1$$$ because $$$2^{i}(c_{i} - 2) + 2^{i + 1}(c_{i + 1} + 1) = 2^{i} c_{i} + 2^{i + 1} c_{i + 1}$$$. Also when we send coins from house $$$n - 1$$$ to house $$$0$$$, $$$I$$$ decreases exactly by $$$2^{n} - 1$$$. So if we send coins from house $$$n - 1$$$ to house 0 $$$k$$$ times, we shall have $$$\sum_{i = 0}^{n - 1} 2^{i} a_{i} - \sum_{i = 0}^{n - 1} 2^{i} b_{i} = k(2^{n} - 1)$$$. From this we can uniquely find the value of $$$k$$$.

We are almost done, first send $$$k$$$ coins to house $$$0$$$ from the last houses greedily. Now we can solve this problem for non-cyclic array which can be done with a simple loop.