P7723 [Ynoi2007] TB5x

This is an interactive problem. Initially, there are $n$ points $(i,p_i)$ on a 2D plane. Each point has a weight $d_i$, with $0\le i

The provided interactive library reads the input data in the following format: - Line 1: $n$. - Next $n$ lines: $p_i\;d_i$ ($d_i$ is represented by two integers). - Line $n+2$: $m$. - Next $m$ lines: $x1_i\;x2_i\;y1_i\;y2_i\;o_i$ ($o_i$ is represented by $9 \times 4$ integers). Elements in $D$ are $2\times 1$ matrices, and elements in $O$ are $2\times 2$ matrices. The entries of the matrices are integers modulo $2^{32}$. $+$ corresponds to matrix addition, and $\cdot$ corresponds to matrix multiplication. You can refer to the implementation of the provided interactive library for details. In the actual judging environment, the input/output format and the definitions of $D,O$, etc. may be different.

The provided interactive library prints your answers in the following format: - For each query, output $13$ lines. Lines $1,2,3,5,6,7,9,10,11$ each contain two integers, which represent, in order, $ans[0][0],ans[0][1],ans[0][2],ans[1][0],ans[1][1],ans[1][2],ans[2][0],ans[2][1],ans[2][2]$ for this query. The other lines are empty lines. - Print the total cost to stderr, and print a warning when the total cost exceeds the cost limit.

Idea: ccz181078, Solution: ccz181078, Code: ccz181078, Data: ccz181078. Special thanks: w33z8kqrqk8zzzx33 modified the interactive library so that it can run on Luogu. For $100\%$ of the data, it holds that $n\le 10^5$ and $m\le 2\times 10^4$. There are 10 test groups in total, with $n=10^5$. For each group, $m$ is respectively $10,100,1000,2000,5000,10000,12500,15000,17500,20000$. The cost limit for all data is $10^8$. Each test group is worth $10$ points. Translated by ChatGPT 5