[USACO24OPEN] Splitting Haybales P

Luogu

IDLGP10284

Time2000ms

Memory256MB

DifficultyP6

USACO平衡树2024均摊分析

Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has $N$ ( $1\le N\le 2\cdot 10^5$) haybales sorted in non-increasing order, where the $i$-th haybale has $a_i$ units of hay ($2\cdot 10^5\ge a_1\ge a_2 \ge \dots \ge a_N \ge 1$). Farmer John is considering splitting a contiguous range of haybales $a_l, \dots, a_r$ between Bessie and Elsie. He has decided to process the haybales in order from $l$ to $r$, and when processing the $i$-th haybale he will give it to the cow who currently has less hay (if it is a tie, he will give it to Bessie). You are given $Q$ ($1\le Q\le 2\cdot 10^5$) queries, each with three integers $l,r,x$ ($1\le l\le r\le N$, $|x|\le 10^9$). For each query, output how many more units of hay Bessie will have than Elsie after processing haybales $l$ to $r$, if Bessie starts with $x$ more units than Elsie. Note that this value is negative if Elsie ends up with more haybales than Bessie. ## Input First line contains $N$. Second line contains $a_1\dots a_N$. Third line contains $Q$. Next $Q$ lines contain $l, r, x$. ## Output Output $Q$ lines, containing the answer for each query. [samples] ## Note ##### For Sample 1: For the 1st query, Elsie starts with $2$ more hay than Bessie. Then, after processing haybale $1$, Bessie will receive $3$ hay, and Bessie will have $1$ more hay than Elsie. For the 3rd query, Elsie and Bessie start with the same number of hay. After processing haybale $1$, Bessie will receive $3$ hay, and Bessie will have $3$ more hay than Elsie. For the 9th query, Bessie starts with $1$ more hay than Elsie, then after processing the 1st haybale, has $2$ less hay than Elsie, and after processing the 2nd haybale, has $1$ less hay than Elsie. ##### For Sample 2: In the 5th query, there are $5$ haybales to process. Bessie receives $4$ hay, then Elsie receives $4$ hay, then Bessie receives $3$ hay, then Elsie receives $1$ hay, then Elsie receives $1$ hay. #### SCORING: - Input 3: $Q\le 100$. - Inputs 4-6: At most $100$ distinct $a_i$. - Inputs 7-22: No additional constraints.

Samples

Input #1

Output #1

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[USACO24OPEN] Splitting Haybales P",
    "description": {
      "content": "Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has $N$ ( $1\\le N\\le 2\\cdot 10^5$) haybales sorted in non-increasing order,  where the $i$-th haybale has ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10284"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Farmer John wants to fairly split haybales between his two favorite cows Bessie and Elsie. He has $N$ ( $1\\le N\\le 2\\cdot 10^5$) haybales sorted in non-increasing order,  where the $i$-th haybale has ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments