I'm ALIVEEEEEEEEEEEEEEEEEE and have internet, bypassed the internet blackout.

It's not fun, not cool, boring, based, cringe, and also makes ratism harder.
The only use is to trip up your friends the first time they see it.

Hello Codeforces community, This is an editorial for an 11-year-old problem in CF, and the official editorial still has it TODO, so yeah, why not?

319E - Ping-Pong

I'll use step-by-step guides to demonstrate the path to finding the solution to this problem, and I hope it will be helpful to other people.

Note: in this editorial, it's assumed that the interval's ranges don't exceed $$$2n$$$, you can get the queries offline and compress the intervals.

The Main Idea

Let's assume that the intervals are given first offline, then the queries are asked; Also, let's assume $$$n \le 1000$$$.

Let's us define an edge from interval $$$i$$$ to $$$j$$$ bidirectional when $$$i$$$, $$$j$$$ intersect but none of which contains the other(e.g. [1, 10] and [5, 15]).
And an edge unidirectional from $$$i$$$ to $$$j$$$ when $$$i$$$ is contained within $$$j$$$.
Now we can use 2 unidirectional edges to form a bidirectional edge.

We draw a unidirectional edge from interval $$$i$$$ to $$$j$$$, when we can directly get to $$$j$$$ from $$$i$$$. Let this graph be $$$G$$$. Take an Scc from $$$G$$$, $$$C$$$. What we can notice in this graph is that there is a path between all pairs of vertices in $$$C$$$. So let's condensate the Scc‌s into single vertices and create the condensation graph. Let $$$L_C$$$ be the minimum $$$l$$$ in all of the intervals of $$$C$$$, $$$R_C$$$ is similarly defined.

Due to intervals lengths being strictly increasing(The whole reason this solution works), We can notice that for 2 Scc‌s, $$$C_1$$$ and $$$C_2$$$, there is a path going from $$$C_1$$$ to $$$C_2 \iff L_{C_2} \le L_{C_1} \text{ and } R_{C_1} \le R_{C_2}$$$. (this condition is useful So let's name it $$$\ast$$$)

Now, we can loop over all pairs of intervals, add the edges accordingly, and find the strongly connected components of each interval.
For a query, if the intervals are in the same Scc or $$$\ast$$$ is satisfied, the answer is Yes otherwise No.

Getting rid of Scc

After a bit of thinking, you can notice that drawing unidirectional edges is useless, because of the $$$\ast$$$ we can easily get rid of them, Let's use a Union Find Tool (aka dsu), to easily manage the connected components, we will only add the bidirectional edges, and merge their components while taking care of $$$L$$$ and $$$R$$$ in the merging process. The query handling is similar.

$$$n \le 10^5$$$

Note: this is just the magic of data structures, specifically segment trees.
Let's use a segment tree to handle component merging faster. In the segment tree nodes, we store a list of leaders of the DSU components where they strictly contain the range of this node.
Let's assume that we're adding the interval $$$[l, r]$$$, due to the length strictly increasing nature, we can trace the path of $$$l$$$ from the segment tree root to the leaf, and merge the current interval's component with the components store in the nodes of the path, we do the same for $$$r$$$.
Let the component of the current interval be $$$C$$$ after merging, now we must add this component to the nodes of $$$(L_C, R_C)$$$ range in the segment tree; so the other intervals can merge with the current interval.
Also note that while adding the interval $$$[l, r]$$$, after passing through a node, we'll clear its list of leaders.

The query handling is the same.

The full solution

Now it's just left to put the puzzle pieces together. First, we'll Get all the queries offline, So we can compress the intervals.

Now let's iterate through the queries, if the current query is an addition query, we'll just replace $$$[l, r]$$$ with their compressed equivalent, and add the interval using the previously mentioned technique with a segment tree.
Otherwise: If the intervals were in the same component, or $$$\ast$$$ was satisfied, output Yes, otherwise No.

Code

285883385

#include <bits/stdc++.h>
using namespace std;
// * No One Dies a Virgin, Life Fucks Us All
typedef long long ll;
#define nl '\n'
#define ff first
#define ss second
#define pb push_back
#define sik(x) {cout << x << nl; return;}
constexpr ll maxn = 1e6+10, mod = 1e9 + 7, inf = 1e17, SQ = 450, P = 6065621, maxlg = 20;
typedef pair<ll, ll> pii;

struct query {
  ll id, l, r;
  query() {}
  query(ll id, ll l, ll r) : id(id), l(l), r(r) {}
};

ll n, f[maxn], L[maxn], R[maxn];
vector<ll> cmp, seg[maxn << 2];
vector<query> Q;

inline void init() {
  for (int i = 0 ; i < maxn ; i ++) {
    f[i] = -1;
  }
}

ll get(ll v) {
  if (f[v] < 0) return v;
  return f[v] = get(f[v]);
}

inline void merge(ll u, ll v) {
  u = get(u), v = get(v);
  if (u == v) return;
  if (-f[u] < -f[v]) swap(u, v);
  f[u] += f[v];
  f[v] = u;

  L[u] = min(L[u], L[v]);
  R[u] = max(R[u], R[v]);
}

void mrg(ll x, ll v, ll l = 0, ll r = maxn, ll id = 1) {
  for (int i : seg[id]) {
    merge(i, v);
  }
  seg[id].clear();

  if (r - l <= 1) return;
  ll mid = (l + r) >> 1, lc = id << 1, rc = lc | 1;
  if (x < mid) mrg(x, v, l, mid, lc);
  else mrg(x, v, mid, r, rc);
}

void add(ll ql, ll qr, ll v, ll l = 0, ll r = maxn, ll id = 1) {
  if (ql <= l && r <= qr) {
    seg[id].pb(v);
    return;
  }
  if (qr <= l || r <= ql) return;
  ll mid = (l + r) >> 1, lc = id << 1, rc = lc | 1;
  add(ql, qr, v, l, mid, lc);
  add(ql, qr, v, mid, r, rc);
}

void input() {
  cin >> n;
  Q.resize(n);

  for (int i = 0 , cnt = 0,  t , a , b ; i < n ; i ++) {
    cin >> t >> a >> b;
    if (t == 1) {
      cnt ++;
      Q[i] = query(cnt, a, b);
      cmp.pb(a);
      cmp.pb(a + 1); // for handling the (a, b) range in the segment addition
      cmp.pb(b);
    } else Q[i] = query(-1, a, b);
  }
}

void compress() {
  sort(cmp.begin(), cmp.end());
  cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
  for (query& q : Q) {
    if (q.id != -1) {
      q.l = lower_bound(cmp.begin(), cmp.end(), q.l) - cmp.begin();
      q.r = lower_bound(cmp.begin(), cmp.end(), q.r) - cmp.begin();
    }
  }
}

int32_t main() {
  cin.tie(0)->sync_with_stdio(0); 
  init();
  input();
  compress();

  for (query& q : Q) {
    if (q.id != -1) { // new interval
      auto [id, l, r] = q;
      L[id] = l;
      R[id] = r;
      mrg(l, id);
      mrg(r, id);
      ll x = get(id);
      add(L[x] + 1, R[x], id);
    } else {
      auto [id, a, b] = q;
      a = get(a), b = get(b);
      if (a == b || (L[b] <= L[a] && R[a] <= R[b])) cout << "YES\n";
      else cout << "NO\n";
    }
  }

  return 0;
}

Thanks for your time, I hope it was useful.
this was mainly a challenge for me, to formalize my solution.

A Question

What if the interval lengths weren't necessarily increasing? Now what.
Since the main reason this solution works, is that we're guaranteed that after an interval is added, there won't be any interval added which will be completely inside of it, because it'll create a bidirectional edge between them which is incorrect.

In a weird high school, there are $$$n$$$ students, and the school principal Mr. X wants to make students happy so he decides to throw a couples' party.
In this high school, between every 2 person, there can be 4 types of relationships:
1: they love each other
2: The first loves the second but the second doesn't
3: The second loves the first but the first doesn't
4: they don't like each other

At this party, people will be grouped into Pairs of couples.
The relationship between them determines the happiness of a pair:
type 1: happiness 2, type 2,3: happiness 1, type 4: happiness -1
if a person gets left out(I.E n is odd) there will be a -2 happiness for him

Since Mr. X is a happy person he wants to maximize the sum happiness of the party. Since he is a busy person He asks you to do that

Input Format
In The First Line, there will be one integer $$$n$$$: $$$n$$$, ($$$1 \leq n \leq 10^5$$$) the number of people at the party. In the Second line will be $$$m$$$, the number of people who love a person ($$$1 \leq r \leq 10^5$$$)
In the following $$$m$$$ lines there will be a format: two indexes $$$i$$$, $$$j$$$ meaning the person $$$i$$$ loves the person $$$j$$$. (Two-sided love will be given in 2 separate lines, if there isn't a directed edge between 2 people their relationship is type 4)

Output Format In the only line of the output, print the maximum happiness of the party

So today I came up with this problem and actually got stuck in solving it. Appreciate any helps

Hello, CF community, I found this 1700*-ish problem, can somebody help?

Given $$$n$$$, $$$d$$$ positive integers, and the array $$$a$$$ with length $$$n$$$
for each $$$i$$$ s. t $$$1 \leq i \leq n$$$
Find the maximum j s. t $$$\vert{a_i - a_j}\vert \leq d$$$

Input format:
Integers n,d: $$$1 \leq n \leq 1e5, 1 \leq d \leq 1e9$$$
In the next line given $$$n$$$ integers representing $$$a_1$$$, $$$a_2$$$, ..., $$$a_{n-1}$$$, $$$a_n$$$

Output format:
In single line for each $$$1 \leq i \leq n$$$ output the corresponding $$$j$$$
if there is no corresponding $$$j$$$ output -1

I'd appreciate a solution without any kind of advanced data structure(___Trees, ___Arrays, etc)
Thanks for any help