J. The Power of the Dark Side - 2

Codeforces

IDCF10221J

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

On the Jedi Tournament $n$ Jedi are battling each other. Every Jedi has three parameters: strength, agility and intelligence. When two Jedi have a fight, the winner will be the Jedi which has at least two parameters higher compared to the same parameters of his opponent. For example, Jedi with parameters (5, 9, 10) defeats Jedi with parameters (2, 12, 4) because of first and third parameters. Sith have a plan to turn one of the Jedi to the dark side of the Force. It will give him a powerful skill that allows to set all his parameters arbitrarily before every fight, with the restrictions that the parameters should remain non-negative integers and their sum should not change. For every Jedi, determine how many other Jedi he can defeat being turned to the dark side. The first line contains a single integer $n$ ($1 <= n <= 500000$) — the number of the Jedi. Each of the next $n$ lines contains three integers $a_i$, $b_i$ and $c_i$ ($0 <= a_i, b_i, c_i <= 10^9$) — the parameters of the Jedi. Output $n$ integers: how many other Jedi the $i$-th Jedi can defeat being turned to the dark side. ## Input The first line contains a single integer $n$ ($1 <= n <= 500000$) — the number of the Jedi.Each of the next $n$ lines contains three integers $a_i$, $b_i$ and $c_i$ ($0 <= a_i, b_i, c_i <= 10^9$) — the parameters of the Jedi. ## Output Output $n$ integers: how many other Jedi the $i$-th Jedi can defeat being turned to the dark side. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ with $ 1 \leq n \leq 2.2 \times 10^6 $. For each day $ d \in \{0, 1, \dots, n-1\} $, define the capacity $ c_d $ as the number of pairs $ (i, j) \in \{0, 1, \dots, n-1\}^2 $ such that $ (i \cdot j) \bmod n = d $. **Constraints** $ 1 \leq n \leq 2.2 \times 10^6 $ **Objective** Compute the vector $ (c_0, c_1, \dots, c_{n-1}) $, where $$ c_d = \left| \left\{ (i, j) \in \{0, 1, \dots, n-1\}^2 \mid (i \cdot j) \bmod n = d \right\} \right| \quad \text{for each } d \in \{0, 1, \dots, n-1\}. $$

API Response (JSON)

{
  "problem": {
    "name": "J. The Power of the Dark Side - 2",
    "description": {
      "content": "On the Jedi Tournament $n$ Jedi are battling each other. Every Jedi has three parameters: strength, agility and intelligence. When two Jedi have a fight, the winner will be the Jedi which has at least",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10221J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On the Jedi Tournament $n$ Jedi are battling each other. Every Jedi has three parameters: strength, agility and intelligence. When two Jedi have a fight, the winner will be the Jedi which has at least...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ with $ 1 \\leq n \\leq 2.2 \\times 10^6 $.  \nFor each day $ d \\in \\{0, 1, \\dots, n-1\\} $, define the capacity $ c_d $ as the number of pairs $ (i, j) \\in \\{0,...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments