[USACO24FEB] Milk Exchange G

Luogu

IDLGP10194

Time2000ms

Memory256MB

DifficultyP5

USACO2024O2优化前缀和差分单调栈

Farmer John 的 $N$（$1\le N \le 5\cdot 10^5$）头奶牛排成一圈。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\le a_i\le 10^9$）升的桶。所有桶初始时都是满的。每一分钟，对于 $1\le i<N$，奶牛 $i$ 会将其桶中所有牛奶传递给奶牛 $i+1$，奶牛 $N$ 将其牛奶传递给奶牛 $1$。所有交换同时发生（即，如果一头奶牛的桶是满的，送出 $x$ 升牛奶同时收到 $x$ 升，则她的牛奶量保持不变）。如果此时一头奶牛的牛奶量超过 $a_i$，则多余的牛奶会损失。在 $1,2,\ldots,N$ 的每一分钟后，所有奶牛总共还余下多少牛奶？ ## Input 输入的第一行包含 $N$。第二行包含 $a_1,a_2,\ldots,a_N$。 ## Output 输出 $N$ 行，其中第 $i$ 行包含 $i$ 分钟后所有奶牛总共余下的牛奶量。 [samples] ## Note ### 样例解释 1 最初，每个桶中的牛奶量为 $[2,2,2,1,2,1]$。 - $1$ 分钟后，每个桶中的牛奶量为 $[1,2,2,1,1,1]$，因此总牛奶量为 $8$。 - $2$ 分钟后，每个桶中的牛奶量为 $[1,1,2,1,1,1]$，因此总牛奶量为 $7$。 - $3$ 分钟后，每个桶中的牛奶量为 $[1,1,1,1,1,1]$，因此总牛奶量为 $6$。 - $4$ 分钟后，每个桶中的牛奶量为 $[1,1,1,1,1,1]$，因此总牛奶量为 $6$。 - $5$ 分钟后，每个桶中的牛奶量为 $[1,1,1,1,1,1]$，因此总牛奶量为 $6$。 - $6$ 分钟后，每个桶中的牛奶量为 $[1,1,1,1,1,1]$，因此总牛奶量为 $6$。 ### 样例解释 2 $1$ 分钟后，每个桶中的牛奶量为 $[1,3,6,4,4,3,3,1]$，因此总牛奶量为 $25$。 ### 测试点性质 - 测试点 $4-5$：$N\le 2000$。 - 测试点 $6-8$：$a_i\le 2$。 - 测试点 $9-13$：所有 $a_i$ 在范围 $[1,10^9]$ 内均匀随机生成。 - 测试点 $14-23$：没有额外限制。

Samples

Input #1

6
2 2 2 1 2 1

Output #1

Input #2

8
3 8 6 4 8 3 8 1

Output #2

Input #3

10
9 9 10 10 6 8 2 1000000000 1000000000 1000000000

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[USACO24FEB] Milk Exchange G",
    "description": {
      "content": "Farmer John 的 $N$（$1\\le N \\le 5\\cdot 10^5$）头奶牛排成一圈。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\\le a_i\\le 10^9$）升的桶。所有桶初始时都是满的。 每一分钟，对于 $1\\le i<N$，奶牛 $i$ 会将其桶中所有牛奶传递给奶牛 $i+1$，奶牛 $N$ 将其牛奶传递给奶牛 $1$。所有交换同时发生（即，如果一头奶牛的桶是满",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10194"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John 的 $N$（$1\\le N \\le 5\\cdot 10^5$）头奶牛排成一圈。第 $i$ 头奶牛有一个容量为整数 $a_i$（$1\\le a_i\\le 10^9$）升的桶。所有桶初始时都是满的。\n\n每一分钟，对于 $1\\le i<N$，奶牛 $i$ 会将其桶中所有牛奶传递给奶牛 $i+1$，奶牛 $N$ 将其牛奶传递给奶牛 $1$。所有交换同时发生（即，如果一头奶牛的桶是满...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments