{"problem":{"name":"F. New Year and Rainbow Roads","description":{"content":"Roy and Biv have a set of _n_ points on the infinite number line. Each point has one of 3 colors: red, green, or blue. Roy and Biv would like to connect all the points with some edges. Edges can be ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF908F"},"statements":[{"statement_type":"Markdown","content":"Roy and Biv have a set of _n_ points on the infinite number line.\n\nEach point has one of 3 colors: red, green, or blue.\n\nRoy and Biv would like to connect all the points with some edges. Edges can be drawn between any of the two of the given points. The cost of an edge is equal to the distance between the two points it connects.\n\nThey want to do this in such a way that they will both see that all the points are connected (either directly or indirectly).\n\nHowever, there is a catch: Roy cannot see the color red and Biv cannot see the color blue.\n\nTherefore, they have to choose the edges in such a way that if all the red points are removed, the remaining blue and green points are connected (and similarly, if all the blue points are removed, the remaining red and green points are connected).\n\nHelp them compute the minimum cost way to choose edges to satisfy the above constraints.\n\n## Input\n\nThe first line will contain an integer _n_ (1 ≤ _n_ ≤ 300 000), the number of points.\n\nThe next _n_ lines will contain two tokens _p__i_ and _c__i_ (_p__i_ is an integer, 1 ≤ _p__i_ ≤ 109, _c__i_ is a uppercase English letter '_R_', '_G_' or '_B_'), denoting the position of the _i_\\-th point and the color of the _i_\\-th point. '_R_' means red, '_G_' denotes green, and '_B_' means blue. The positions will be in strictly increasing order.\n\n## Output\n\nPrint a single integer, the minimum cost way to solve the problem.\n\n[samples]\n\n## Note\n\nIn the first sample, it is optimal to draw edges between the points (1,2), (1,4), (3,4). These have costs 4, 14, 5, respectively.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Roy 和 Biv 在无限数轴上有一组 #cf_span[n] 个点。\n\n每个点具有三种颜色之一：红色、绿色或蓝色。\n\nRoy 和 Biv 希望用一些边连接所有点。边可以在任意两个给定点之间绘制，一条边的代价等于它连接的两点之间的距离。\n\n他们希望以这样的方式选择边：使得他们两人都能看到所有点被连接（直接或间接）。\n\n然而，有一个限制：Roy 看不见红色，Biv 看不见蓝色。\n\n因此，他们必须选择边，使得如果移除所有红色点，剩余的蓝色和绿色点仍然连通（同样地，如果移除所有蓝色点，剩余的红色和绿色点也仍然连通）。\n\n请帮助他们计算满足上述约束的最小代价连接方式。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 300 000]），表示点的数量。\n\n接下来的 #cf_span[n] 行每行包含两个标记 #cf_span[pi] 和 #cf_span[ci]（#cf_span[pi] 是一个整数，#cf_span[1 ≤ pi ≤ 109]，#cf_span[ci] 是一个大写英文字母 '_R_'、'_G_' 或 '_B_'），分别表示第 #cf_span[i] 个点的位置和颜色。'_R_' 表示红色，'_G_' 表示绿色，'_B_' 表示蓝色。位置将按严格递增顺序给出。\n\n请输出一个整数，表示解决该问题的最小代价。\n\n在第一个样例中，最优方案是连接点对 (1,2)、(1,4)、(3,4)。这些边的代价分别为 4、14、5。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 300 000]），表示点的数量。接下来的 #cf_span[n] 行每行包含两个标记 #cf_span[pi] 和 #cf_span[ci]（#cf_span[pi] 是一个整数，#cf_span[1 ≤ pi ≤ 109]，#cf_span[ci] 是一个大写英文字母 '_R_'、'_G_' 或 '_B_'），分别表示第 #cf_span[i] 个点的位置和颜色。'_R_' 表示红色，'_G_' 表示绿色，'_B_' 表示蓝色。位置将按严格递增顺序给出。\n\n## Output\n\n请输出一个整数，表示解决该问题的最小代价。\n\n[samples]\n\n## Note\n\n在第一个样例中，最优方案是连接点对 (1,2)、(1,4)、(3,4)。这些边的代价分别为 4、14、5。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of points.  \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a strictly increasing sequence of positions, where $ p_i \\in \\mathbb{Z}^+ $, $ 1 \\leq p_i \\leq 10^9 $.  \nLet $ C = (c_1, c_2, \\dots, c_n) $ be the sequence of colors, where $ c_i \\in \\{R, G, B\\} $.  \n\nLet $ V_R = \\{ i \\mid c_i = R \\} $, $ V_B = \\{ i \\mid c_i = B \\} $, $ V_G = \\{ i \\mid c_i = G \\} $ be the index sets of red, blue, and green points respectively.  \n\nLet $ G = (V, E) $ be an undirected graph with vertex set $ V = \\{1, 2, \\dots, n\\} $ and edge set $ E \\subseteq \\binom{V}{2} $.  \nThe cost of edge $ (i, j) $ is $ |p_i - p_j| $.  \n\n**Constraints**  \n1. The graph $ G $ must be connected.  \n2. The subgraph induced by $ V \\setminus V_R $ (i.e., blue and green points) must be connected.  \n3. The subgraph induced by $ V \\setminus V_B $ (i.e., red and green points) must be connected.  \n\n**Objective**  \nMinimize the total edge cost:  \n$$\n\\min_{E} \\sum_{(i,j) \\in E} |p_i - p_j|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF908F","tags":["graphs","greedy","implementation"],"sample_group":[["4\n1 G\n5 R\n10 B\n15 G","23"],["4\n1 G\n2 R\n3 B\n10 G","12"]],"created_at":"2026-03-03 11:00:39"}}