[USACO23FEB] Hungry Cow P

Luogu

IDLGP9130

Time6000ms

Memory512MB

DifficultyP6

线段树USACO2023分治

**Note: The time limit for this problem is 6s, three times the default. The memory limit for this problem is 512MB, twice the default.** Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day $d_i$, Farmer John sends a delivery of $b_i$ haybales $(1 \le d_i \le 10^{14}, 0 \le b_i \le 10^9)$. Process $U(1 \le U \le 10^5)$ updates as follows: Given a pair $(d,b)$, update the number of haybales arriving on day $d$ to $b$. After each update, output the sum of all days on which Bessie eats haybales modulo $10^9+7$. ## Input $U$, followed by $U$ lines containing the updates. ## Output The sum after each update modulo $10^9+7$. [samples] ## Note ### Explanation for Sample 1 Answers after each update: $4+5+6=15$ $1+2+3+4+5+6+7+8=36$ $1+2+4+5+6=18$ ### SCORING - Input $3$: $U \le 5000$ - Inputs $4-10$: Updates only increase the number of haybales arriving on day $d$. - Inputs 11-22: No additional constraints.

Samples

Input #1

Output #1

15
36
18

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[USACO23FEB] Hungry Cow P",
    "description": {
      "content": "**Note: The time limit for this problem is 6s, three times the default. The memory limit for this problem is 512MB, twice the default.**  Bessie is a hungry cow. Each day, for dinner, if there is a h",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9130"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**Note: The time limit for this problem is 6s, three times the default. The memory limit for this problem is 512MB, twice the default.** \n\nBessie is a hungry cow. Each day, for dinner, if there is a h...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments