For problem G I found some $$$O(Qlog^3N)$$$ solution then I thought simple $$$O(QN)$$$ would behave better than that so I ended up coding $$$O(QN)$$$ solution and it passed with $$$~1.5$$$ s. IDK if this was intended but that's how I will become yellow on Atcoder.

Atcoder BEGINNER contest they said...

E is nice though.

Was somewhat wiered for me, not able to solve B and C. B I dont know, maybe persistently typing something trivial wrong. With C I was not able to see the dp.

However, D was streight forward, and solved E after some thinking using a lazy segment tree just in time.

For python users, when you see a problem (like today's D) that reads "setter clearly thinks just use cpp::std::map or set" what's your go-to replacement and why? I've tended to google 'pyrival sortedlist' and just use that out of habit.

In hindsight, the problem is a little DSU-y...? but I don't think that was intended, or if you did choose that, I'd love to hear what your recognition points are...?

How to solve $$$E$$$?

The "Pigeonhole Principle" analysis in problem F is so fascinating! At first sight, I think the algorithm has a huge complexity, but if we count all the operations on the number of pairs of T-nodes, the total complexity is in fact bounded by $$$O(T^2)$$$.

Perhaps this is somehow similar to amortized analysis. Really a cool problem, thanks to the problem writers.

Someone please explain the pigeonhole principle in problem F

Concerning problem E — At Least One, I'm having problems checking if a specific segment satisfies the conditions. My solution differs from the editorial and I can't get it to work (probably because it's incorrect).

Can anyone confirm (or disprove) the below statement? If it is correct then the problem is in my implementation.

A segment $$$[L,R]$$$ satisfies the conditions if and only if

$$$\displaystyle L \leq \min_{i=1}^N B_i$$$ (1), $$$\displaystyle R\geq \max_{i=1}^N A_i$$$ (2), $$$\displaystyle R\geq \max_{A_i < L} B_i$$$ (3) (basically I am checking that there is no pair $$$A_j < B_j$$$ such that $$$A_j<B_j<L$$$ (1) or $$$A_j<L\leq R < B_j$$$ (3) or $$$R<A_j<B_j$$$ (2), which I believe are all the bad cases).

Note: I fail 4/12 cases (1 of which is named "04_corner_02" so I am afraid I am missing something).

Alternative solution for B, let's sort the index array instead of the data array.

sort(v.begin() + x + y, v.end(), [&](int l, int r) {
    return make_pair(-(a[l] + b[l]), l) < make_pair(-(a[r] + b[r]), r);
});

For Problem D, I am using this code but this is giving me TLE. I am really surprised by this behaviour. Its O(nlogn), how can it be TLE.

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

void solve() {
  int n, m;
  cin >> n >> m;

  vector<int> arr(n);
  for (int i = 0; i < n; ++i)
    cin >> arr[i];

  vector<int> ans(n, -1);
  set<int> active;
  vector<int> group_map(n + 1, -1);
  vector<vector<int>> groups;
  int group_id = 0;

  for (int i = 0; i < n; ++i) {
    int curr = arr[i];
    auto it = upper_bound(active.begin(), active.end(), curr);

    if (it == active.end()) {
      groups.push_back({curr});
      group_map[curr] = group_id++;
    } else {
      int next = *it;
      active.erase(it);
      group_map[curr] = group_map[next];
      groups[group_map[curr]].push_back(curr);
    }

    if ((int)groups[group_map[curr]].size() == m) {
      for (int j : groups[group_map[curr]])
        ans[j - 1] = i + 1;
    } else {
      active.insert(curr);
    }
  }

  for (int i = 0; i < n; ++i)
    cout << ans[i] << " ";
  cout << endl;
}