問題一覧 > スコア問題

No.5010 Better Mo's Algorithm is Needed!! (Unweighted)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 31
作問者 : butsurizuki
お気に入りにしたユーザー ProblemId : 8810 / 自分の提出
問題文最終更新日: 2022-12-17 00:34:02
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2022 (順位表) の他の問題:

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)
This problem is Problem 1.
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.
The overall ranking will be tallied manually after the contest period ends.

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.
No rejudging, system tests, or the like are planned after the contest period ends.
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]$.
Method 2:
  • 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$.
From the above, the score for this output is $250000000000000$.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。