My editorial for 319E Ping Pong

Правка en2, от bgopc, 2024-10-14 16:42:28

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.

1. The intervals are given offline.

In this subtask, let's assume that the intervals are given to us, and the queries are asked after all the intervals are given.

1.1. $$$n \le 1000$$$

Note: this is the whole intuition behind the main solution.
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 intervals of C, R_C is similarly defined$$$

Теги segment tree, dsu, coordinate compression, ping pong 319e

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский bgopc 2024-10-18 18:59:10 256
en17 Английский bgopc 2024-10-14 18:25:47 30
en16 Английский bgopc 2024-10-14 18:24:37 2738 Tiny change: '(long)">\n\n~~~~~\n#' -> '(long)">\n~~~~~\n#'
en15 Английский bgopc 2024-10-14 18:20:38 4
en14 Английский bgopc 2024-10-14 17:31:17 0 (published)
en13 Английский bgopc 2024-10-14 17:31:02 139
en12 Английский bgopc 2024-10-14 17:28:34 78
en11 Английский bgopc 2024-10-14 17:26:44 4
en10 Английский bgopc 2024-10-14 17:26:01 4
en9 Английский bgopc 2024-10-14 17:25:24 4 Tiny change: 'e minimum _l_ in all of' -> 'e minimum $l$ in all of'
en8 Английский bgopc 2024-10-14 17:24:16 735
en7 Английский bgopc 2024-10-14 17:17:23 714 Tiny change: 'similar.\n' -> 'similar.\n\n\n## $n \le 10^5$'
en6 Английский bgopc 2024-10-14 17:05:23 220
en5 Английский bgopc 2024-10-14 17:02:53 443 Tiny change: ' are asked.\nLet's assum' -> ' are asked;\nAlso let's assum'
en4 Английский bgopc 2024-10-14 16:54:46 616
en3 Английский bgopc 2024-10-14 16:48:30 265 Tiny change: 'e minimum _l_ in all of' -> 'e minimum l in all of'
en2 Английский bgopc 2024-10-14 16:42:28 812
en1 Английский bgopc 2024-10-14 16:28:07 572 Initial revision (saved to drafts)