P17085 [COTS 2026] Atoms / Atomi (No testdata yet).

2s, 512M

There are $N$ atoms in a line, numbered from left to right as $1\sim N$. Atom $i$ has mass $w_i$, and its initial moving direction is either left or right. All atoms start moving at the same time in their initial directions. The distance between adjacent atoms is equal, and all atoms move at the same constant speed. When two atoms with masses $x$ and $y$ collide, nuclear fusion happens: they merge into a new atom with mass $x + y$. The new atom continues moving in the direction of the heavier one among the two colliding atoms. If their masses are equal, the new atom moves to the right. After a sufficiently long time, no more collisions will happen. Divide the remaining atoms into two groups: those moving left and those moving right. We want to know the total mass of the first group and the total mass of the second group. You need to answer $Q$ queries. In the $i$-th query, you are given two numbers $l_i$ and $r_i$. If we only observe atoms $l_i, l_i + 1, \dots , r_i$ (ignoring all other atoms), find the total mass of the two groups. For each query, output the total mass of atoms that finally move left and the total mass of atoms that finally move right.

The first line contains a positive integer $N$ ($1 \le N \le 3 \cdot 10^5$), representing the number of atoms. In each of the next $N$ lines, the $i$-th line contains a positive integer $w_i$ ($1 \le w_i \le 10^9$) and a character $c_i$ ($c_i\in \{\texttt{L},\texttt{R}\}$), representing the mass and the initial direction of the $i$-th atom. The character $c_i$ is `L` if the atom initially moves left, and `R` if it initially moves right. The next line contains a positive integer $Q$ ($1 \le Q \le 3 \cdot 10^5$), representing the number of queries. Each of the next $Q$ lines contains two positive integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le N$), representing the segment boundaries of the $i$-th query.

For each query, output two integers: the total mass of atoms that finally move left, and the total mass of atoms that finally move right.

### Sample Explanation The following is the explanation for sample $1$. In the first query, we observe all five atoms. The second and third atoms merge into an atom of mass $6$ moving left, and the fourth and fifth atoms merge into an atom of mass $8$ moving right. The first atom continues moving left, so the answer is $11$ and $8$. In the fourth query, we observe the third and fourth atoms. Since they move away from each other, they will not collide, so the answer is $4$ and $7$. ### Subtasks | Subtask | Score | Limit | |:---:|:---:|---| | $1$ | $11$ | $N, Q \le 1\,000$ | | $2$ | $9$ | For each query $i$, $l_i = 1$. | | $3$ | $10$ | Initially, there is exactly one atom moving right. | | $4$ | $24$ | There exists $0 \le k \le N$ such that atoms $1, \dots, k$ move right, and atoms $k + 1, \dots, N$ move left. | | $5$ | $21$ | $N \le 3 \cdot 10^4$ | | $6$ | $25$ | No additional constraints. | Translated by ChatGPT 5