E. Chi's performance

Codeforces

IDCF10230E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Chi is a little kid that goes to a middle school in London, Ontario. He is in a band, and they are planning on performing this weekend. There are $N$ members in this band, and each one is categorized by the id of the instrument that they play, represented by a number $V$, and their ability level represented by a number $P$. The enjoyment of a performance depends on the order in which people play, and their ability levels. The playing order goes as follows: *the order of people presenting has to be in the order of their instrument's id, from smallest to largest*, and in case of ties any order of the people with the same instrument is valid. If two people in a row are playing the same instrument, the enjoyment level doesn't change. If two people in a row have different instruments, the enjoyment increases by the absolute diference of their ability levels, because people like to see very different kinds of performances even if the ability level decreases. Chi wants to have the best performance ever, and he asked your help with this task. He wants to know what is the highest enjoyment of the performance, given an optimal ordering. The first line will have an integer $N$ $(1 <= N <= 10^6)$. $N$ lines will follow. The $i$-th line will contain two integers $V_i$ $(1 <= V_i <= 10^9)$ and $P_i$ $(0 <= P_i <= 10^9)$ each, representing the $i$-th person's instrument id and ability level respectively. Print a single number, representing the highest enjoyment possible of the performance, given an optimal ordering of the players. ## Input The first line will have an integer $N$ $(1 <= N <= 10^6)$. $N$ lines will follow. The $i$-th line will contain two integers $V_i$ $(1 <= V_i <= 10^9)$ and $P_i$ $(0 <= P_i <= 10^9)$ each, representing the $i$-th person's instrument id and ability level respectively. ## Output Print a single number, representing the highest enjoyment possible of the performance, given an optimal ordering of the players. [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ denote the number of boxes and number of operations, respectively. Let $ B = (B_1, B_2, \dots, B_n) $ be a tuple of multisets, where $ B_i $ contains integers written on paper strips in box $ i $. For an operation of type 1 (by _wang9897_): - Given $ x_i \in \{1, \dots, 9\} $, $ l_i, r_i \in \mathbb{Z} $, $ c_i \in \mathbb{Z}_{\ge 0} $, - For each $ k \in \{1, 2, \dots, r_i - l_i + 1\} $: - Let $ d_k = \overline{\underbrace{x_i x_i \dots x_i}_{c_i + k \text{ digits}}} = x_i \cdot \frac{10^{c_i + k} - 1}{9} $, - Add $ d_k $ to $ B_{l_i + k - 1} $. For an operation of type 2 (by _qkoqhh_): - Given $ l_i, r_i \in \mathbb{Z} $, - Let $ S = \bigcup_{j = l_i}^{r_i} B_j $ be the multiset of all paper strips in boxes $ l_i $ to $ r_i $, - Let $ |S| $ be the total number of strips in this range. **Constraints** 1. $ 1 \le n \le 10^4 $, $ 1 \le m \le 10^5 $ 2. $ 1 \le l_i \le r_i \le n $ 3. $ 1 \le x_i \le 9 $, $ 0 \le c_i \le 10^9 $ 4. All arithmetic is modulo $ M = 1000000007 $ **Objective** For each type-2 operation: - If $ |S| = 0 $, output $ 0 $. - Else, compute the expectation: $$ E = \frac{1}{|S|} \sum_{v \in S} v \mod M $$ Output $ E \equiv \left( \sum_{v \in S} v \right) \cdot |S|^{-1} \mod M $, where $ |S|^{-1} $ is the modular multiplicative inverse of $ |S| $ modulo $ M $.

API Response (JSON)

{
  "problem": {
    "name": "E. Chi's performance",
    "description": {
      "content": "Chi is a little kid that goes to a middle school in London, Ontario. He is in a band, and they are planning on performing this weekend. There are $N$ members in this band, and each one is categorized ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10230E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Chi is a little kid that goes to a middle school in London, Ontario. He is in a band, and they are planning on performing this weekend. There are $N$ members in this band, and each one is categorized ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of boxes and number of operations, respectively.  \nLet $ B = (B_1, B_2, \\dots, B_n) $ be a tuple of multisets, where $ B_i $ contains ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments