{"problem":{"name":"I. Useless Pokemino","description":{"content":"Laersh is a Pokemino trainer and he just captured his first pokemino. Throughout his journey he will capture more Pokeminos. Each Pokemino has an attack and a defense level. A Pokemino is better than ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10230I"},"statements":[{"statement_type":"Markdown","content":"Laersh is a Pokemino trainer and he just captured his first pokemino. Throughout his journey he will capture more Pokeminos. Each Pokemino has an attack and a defense level. A Pokemino is better than another one if it has greater attack and greater defense level. Besides capturing Pokeminos, Laersh can breed any two Pokeminos that he owns and generate a new Pokemino. This new Pokemino's attack and defense will be a linear combination of its parents attributes:\n\nAttackchild = Attackparent1 * c + Attackparent2 * (1 - c)\n\nDefensechild = Defenseparent1 * c + Defenseparent2 * (1 - c)\n\nThe number c is the same for attack and defense, and can be any number 0 ≤ c ≤ 1.\n\nAn useless Pokemino is a Pokemino such that Laersh owns a better Pokemino, or he can breed a better Pokemino. For each new Pokemino that Laersh captures, help him figuring out the number of useless Pokeminos that he owns. \n\nThe first line of the input contains one integer N (1 ≤ N ≤ 105). N lines will follow. The i-th line will contain two integers Ai (0 ≤ Ai ≤ 109) and Di (0 ≤ Di ≤ 109) each. Ai represents the attack of Pokemino i and Di represents the defense of Pokemino i. Note: No two captured Pokeminos will have the same attack and defense.\n\nOutput N numbers, the i-th number represents how many useless Pokeminos there are when the i-th Pokemino is captured.\n\n## Input\n\nThe first line of the input contains one integer N (1 ≤ N ≤ 105). N lines will follow. The i-th line will contain two integers Ai (0 ≤ Ai ≤ 109) and Di (0 ≤ Di ≤ 109) each. Ai represents the attack of Pokemino i and Di represents the defense of Pokemino i. Note: No two captured Pokeminos will have the same attack and defense.\n\n## Output\n\nOutput N numbers, the i-th number represents how many useless Pokeminos there are when the i-th Pokemino is captured.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ x \\in \\mathbb{Z} $ be a 128-bit unsigned integer representing an IPv6 address.  \nLet $ H = (h_1, h_2, \\dots, h_8) $ be the 8-section hexadecimal representation of $ x $, where each $ h_i \\in \\{0, 1, \\dots, 65535\\} $ is a 16-bit segment (4 hex digits), obtained by splitting $ x $ into 8 contiguous 16-bit blocks from most to least significant.  \nLet $ \\tilde{H} = (\\tilde{h}_1, \\dots, \\tilde{h}_8) $ be the zero-stripped version of $ H $, where $ \\tilde{h}_i = \\text{hex}(h_i) $ with leading zeros removed (and $ \\tilde{h}_i = \"0\" $ if $ h_i = 0 $).\n\n**Constraints**  \n1. $ 0 \\le x < 2^{128} $  \n2. Each $ h_i $ is a 16-bit segment: $ 0 \\le h_i \\le 65535 $  \n3. The double colon `::` may be used **at most once** and **only to replace a contiguous sequence of two or more zero sections** (i.e., no `::` for a single `0`).  \n\n**Objective**  \nFind the abbreviated representation $ A $ of $ \\tilde{H} $ such that:  \n- `::` replaces a contiguous subsequence $ h_j, h_{j+1}, \\dots, h_{j+k-1} $ where $ k \\ge 2 $ and $ h_i = 0 $ for all $ i \\in [j, j+k-1] $.  \n- Among all valid abbreviations:  \n  (i) Minimize the number of remaining sections (i.e., maximize the length of the zero run replaced by `::`).  \n  (ii) If tied, choose the lexicographically smallest string representation (lex order on the colon-separated hex segments with `::` treated as a single token).  \n\nOutput the unique optimal abbreviation $ A $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10230I","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}