No.1068 #Various Colors / Red and Blue and more various colors (Hard)
タグ : / 解いたユーザー数 107
作問者 :
leafirby
/ テスター :
harady_a_human
No.1066 and this problem are the same problem, but the constraints, the time limit, and the memory limit are different. (Added at 21:30)
Problem Statement
There are $N$ boxes here. The $i(1\leq i\leq N)$-th box contains $A_i$ balls.
More specifically, box $i$ contains exactly $1$ ball of each color, from color $1$ through color $A_i$.
Answer $Q$ queries. The $i(1\leq i\leq Q)$-th query is as follows.
Input
$N\ Q$ $A_1\ A_2\ ...\ A_N$ $B_1\ B_2\ ...\ B_Q$
$1\le N\le 2\times 10^5$
$1\le Q\le min(N+1,5000)$
$1\le A_i\le 10^{18}$
$0\le B_i\le N$
All inputs are integers.
Output
Answer the $Q$ queries, and print a newline at the end.
Sample
Sample 1
Input
3 4 3 4 5 0 1 2 3
Output
24 26 9 1
There are $60$ ways to take the balls in total. Among them, there are $24$ ways in which not even $1$ ball of color $1$ is included.
Sample 2
Input
4 3 1 3 3 3 3 1 4
Output
6 8 1
Sample 3
Input
3 2 5 7 5 1 3
Output
64 1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。