TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

53.3% (8/15)

Submission's AC Ratio

15.7% (48/306)

Tags

Description

Alice and Bob find out a new, cool king game to play, and they want to play the game with you. You will enjoy the game, right?

Alice and Bob will give you two integer sequences $a_1, a_2, \dots, a_N$, $w_1, w_2, \dots, w_N$ with length $N$.

Alice and Bob allow you to do the following operations for many(possibly zero) times:

  • change $a_i$ to any integer, this operation will cost you $w_i$ dollars.

Now, they will give you $Q$ indepenedent queries. In the $i$-th query, they give you four integers $L_i, R_i, x_i, y_i$. They want you to make the integers $a_{L_i}, a_{L_i + 1}, \dots, a_{R_i}$ has $z$ distinct integers, such that $z \in [x_i, y_i]$. Also, since they are poor, they want you to spend as little as possible.

Please write a program to help them calculate the answers (minimum dollar that they have to spend).

小 A 和小 B 最近發現一個酷酷的國王遊戲,他們想和你一起玩。

他們會給你兩個整數序列 $a_1, a_2, \dots, a_N$, $w_1, w_2, \dots, w_N$ 長度皆為 $N$

你可以做以下操作任意多次(可以不做)

  • 把 $a_i$ 改成任意整數 代價為 $w_i$ 元

現在,他們將對你詢問 $Q$ 次 (不同的詢問之間互相獨立 不影響)。 第 $i$ 次詢問,會有四個整數 $L_i, R_i, x_i, y_i$。目標是要讓 $a_{L_i}, a_{L_i+1}, \dots, a_{R_i}$ 中恰有 $z$ 個不同的整數,其中 $z \in [x_i, y_i]$。同時因為他們很窮,所以希望你花越少代價越好

請寫一個程式幫幫他們計算答案 (最少需要花多少錢)

Input Format

The first line of the input contains two integers $N, Q$, indicating the length of the sequences, and the number of queries.

The second line contains $N$ integers $a_1, a_2, \dots, a_N$.

The third line contains $N$ integers $w_1, w_2, \dots, w_N$.

In the following $Q$ lines, the $i$-th line indicates the $i$-th query. The $i$-th line contains four integers $L_i, R_i, x_i, y_i$.

The meanings of the parameters above have been explained in the problem statement.

  • $1 \leq N, Q \leq 10^ 5$
  • $1 \leq a_i, w_i \leq 10^ 5$
  • $1 \leq L_i \leq R_i \leq N$
  • $1 \leq x_i \leq y_i \leq R_i - L_i + 1$

輸入第一行有兩個整數 $N, Q$, 分別代表序列的長度和詢問的數量

第二行有 $N$ 個整數 $a_1, a_2, \dots, a_N$

第三行有 $N$ 個整數 $w_1, w_2, \dots, w_N$

接下來 $Q$ 行之中的第 $i$ 行包含第 $i$ 筆詢問,每行皆有四個整數 $L_i, R_i, x_i, y_i$

各個參數的意義皆在題目中有解釋

  • $1 \leq N, Q \leq 10^ 5$
  • $1 \leq a_i, w_i \leq 10^ 5$
  • $1 \leq L_i \leq R_i \leq N$
  • $1 \leq x_i \leq y_i \leq R_i - L_i + 1$

Output Format

For each query, print the answer to the query in one line.

對於每筆詢問,請各自輸出一行整數代表答案

Sample Input 1

6 4
3 2 3 1 4 2
2 4 3 1 2 2
1 6 1 3
1 6 4 4
1 6 5 6
2 5 1 1

Sample Output 1

1
0
2
6

Hints

Problem Source

2021 台清交程式競賽 pK

Subtasks

No. Testdata Range Score
1 0~37 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 7500 1024000 65536 1
1 7500 1024000 65536 1
2 7500 1024000 65536 1
3 7500 1024000 65536 1
4 7500 1024000 65536 1
5 7500 1024000 65536 1
6 7500 1024000 65536 1
7 7500 1024000 65536 1
8 7500 1024000 65536 1
9 7500 1024000 65536 1
10 7500 1024000 65536 1
11 7500 1024000 65536 1
12 7500 1024000 65536 1
13 7500 1024000 65536 1
14 7500 1024000 65536 1
15 7500 1024000 65536 1
16 7500 1024000 65536 1
17 7500 1024000 65536 1
18 7500 1024000 65536 1
19 7500 1024000 65536 1
20 7500 1024000 65536 1
21 7500 1024000 65536 1
22 7500 1024000 65536 1
23 7500 1024000 65536 1
24 7500 1024000 65536 1
25 7500 1024000 65536 1
26 7500 1024000 65536 1
27 7500 1024000 65536 1
28 7500 1024000 65536 1
29 7500 1024000 65536 1
30 7500 1024000 65536 1
31 7500 1024000 65536 1
32 7500 1024000 65536 1
33 7500 1024000 65536 1
34 7500 1024000 65536 1
35 7500 1024000 65536 1
36 7500 1024000 65536 1
37 7500 1024000 65536 1