No.5010 Better Mo's Algorithm is Needed!! (Unweighted)
タグ : / 解いたユーザー数 31
作問者 :
butsurizuki
Note
For the score ranking of this problem, see here.
https://yukicoder.me/problems/no/5010/score
This problem is Problem 1 of Day 17 of Advent Calendar Contest 2022.
The difficulty is one assigned for the Advent Calendar Contest. You can earn points in the contest as long as you produce a valid output.
Rules
Day 17 of Advent Calendar Contest 2022 (Better Mo's Algorithm is Needed!!) consists of two problems.
- Problem 1: Better Mo's Algorithm is Needed!! (Unweighted)
- Problem 2: Better Mo's Algorithm is Needed!! (Weighted)
The differences from Problem 2 are as follows.
- $WT=1$ is fixed.
- $W_i=100$ is fixed.
- $W$ in Problem 2 is generated so that its expected value is about $50$. Therefore, in Problem 2 you can expect a score of $2$ times that of Problem 1 or more.
The overall ranking for this problem is determined as follows:
- The participant with the higher total of (score of Problem 1) + (score of Problem 2) ranks higher.
- If the order is not determined by the above, the participants are tied.
Since this is a score-based problem, you cannot make another submission for 5 minutes after your last submission.
The rules on discussing this problem during the contest (as intended by the writer) are as follows.
- Discussion and consultation are permitted on matters not directly related to solutions (such as how to test locally).
- Volunteers may create and publish visualizers, and so on.
- Furthermore, you are permitted to directly mention your own solution and to share your code.
- However, if someone else improves their solution as a result, the score belongs to the person who submitted the improved code.
The contest period ends at 2022-12-17 23:30:00, and the seeds used to generate the test cases will be published on the editorial page.
Problem Statement
Weights $W=(W_1,W_2,\dots,W_N)$ are given as a sequence of length $N$.
In addition, $Q$ intervals $[L_i,R_i]$ satisfying $1 \le L_i \le R_i \le N$ are given.
The goal of this problem is to choose a suitable permutation $P=(P_1,P_2,\dots,P_Q)$ of $(1,2,\dots,Q)$ so as to minimize the execution time $T$ defined below.
The execution time $T$ is defined as follows.
- First, let $\displaystyle T=\sum^{R_{P_1}}_{k = L_{P_1}} W_k$.
- Next, for $i=1,2,\dots,Q-1$, do the following.
- Let $[a,b]=[L_{P_i},R_{P_i}],[c,d]=[L_{P_{i+1}},R_{P_{i+1}}]$.
- Let $\alpha = \min(a,c), \beta = \max(a,c)$, and add $\displaystyle \sum^{\beta-1}_{k=\alpha} W_k$ to $T$. When $a=c$, the value added is $0$.
- Let $\gamma = \min(b,d), \delta = \max(b,d)$, and add $\displaystyle \sum^{\delta}_{k=\gamma+1} W_k$ to $T$. When $b=d$, the value added is $0$.
Score
This problem has 120 test cases.
The score for each test case is $\min \left( \rm{round} \displaystyle \left( \frac{10^{18}}{T} \right) , 10^{16} \right)$.
The final score for this problem is the sum of the scores over all test cases.
Input
$N$ $Q$ $WT$ $ST$ $W_1$ $W_2$ $\dots$ $W_N$ $L_1$ $R_1$ $L_2$ $R_2$ $\vdots$ $L_Q$ $R_Q$
Constraints
- All input values are integers.
- $N = 200000$
- $Q = 200000$
- $\color{red}{WT = 1}$
- $1 \le ST \le 3$
- $\color{red}{W_i = 100}$
- $1 \le L_i \le R_i \le N$
$WT$ is an integer representing how $W$ is generated, and $ST$ is an integer representing how the intervals are generated. Details are described below.
Output
Output the permutation $P$ in the following format.
$P_1$ $P_2$ $\dots$ $P_Q$
Input Generation
Let $\rm{rnd}$$(l,r)$ denote a uniform random function that returns an integer between $l$ and $r$, inclusive.
$N=200000,Q=200000$ are fixed.
In this problem, $WT=1$.
When $WT=1$, $W_i=100$ for all $i$.
$ST$ takes one of the values $1,2,3$. The test cases contain the same number of cases for each $ST$.
When $ST=1$, every interval $[L_i,R_i]$ is generated by Method 1.
When $ST=2$, every interval $[L_i,R_i]$ is generated by Method 2.
When $ST=3$, for each interval $[L_i,R_i]$, either Method 1 or Method 2 is chosen independently with equal probability, and the interval is generated by that method.
Method 1:
- Generate $x=$ $\rm{rnd}$$(1,N),y=$ $\rm{rnd}$$(1,N)$.
- If $x>y$, swap $x,y$.
- The generated interval is $[x,y]$.
- Generate $l=$ $\rm{rnd}$$(1,N)$.
- Generate $x=$ $\rm{rnd}$$(1,N-l+1)$, and let $y=x+l-1$.
- The generated interval is $[x,y]$.
Distributed Materials
Get the distributed materials (zip) here.
You may use these materials in your solution, and you may redistribute translations of them into other languages.
Sample
Sample 1
Input
5 6 1 1 100 200 300 400 500 1 3 4 4 2 5 1 5 3 5 2 4
Output
6 5 4 3 1 2
This sample violates the constraints and is not included in the actual input.
- $P_1 = 6$, and at this point $T=900$.
- $P_2 = 5$, and at this point $T=1600$.
- $P_3 = 4$, and at this point $T=1900$.
- $P_4 = 3$, and at this point $T=2000$.
- $P_5 = 1$, and at this point $T=3000$.
- $P_6 = 2$, and at this point $T=4000$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。