ZOJ - 3981

The 2017 China Collegiate Programming Contest Qinhuangdao Site is coming! There will be nnn teams participating in the contest, and the contest will be held on a huge round table with mmm seats numbered from 1 to mmm in clockwise order around it. The iii-th team will be seated on the sis_isi​-th seat.BaoBao, an enthusiast for competitive programming, has made ppp predictions of the contest result before the contest. Each prediction is in the form of (ai,bi)(a_i,b_i)(ai​,bi​), which means the aia_iai​-th team solves a problem during the bib_ibi​-th time unit.As we know, when a team solves a problem, a balloon will be rewarded to that team. The participants will be unhappy if the balloons take almost centuries to come. If a team solves a problem during the tat_ata​-th time unit, and the balloon is sent to them during the tbt_btb​-th time unit, then the unhappiness of the team will increase by tb−tat_b-t_atb​−ta​. In order to give out balloons timely, the organizers of the contest have bought a balloon robot.At the beginning of the contest (that is to say, at the beginning of the 1st time unit), the robot will be put on the kkk-th seat and begin to move around the table. If the robot moves past a team which has won themselves some balloons after the robot’s last visit, it will give all the balloons they deserve to the team. During each unit of time, the following events will happen in order:The robot moves to the next seat. That is to say, if the robot is currently on the iii-th (1≤i<m1 \le i < m1≤i<m) seat, it will move to the (i+1i+1i+1)-th seat; If the robot is currently on the mmm-th seat, it will move to the 1st seat.The participants solve some problems according to BaoBao’s prediction.The robot gives out balloons to the team seated on its current position if needed.BaoBao is interested in minimizing the total unhappiness of all the teams. Your task is to select the starting position kkk of the robot and calculate the minimum total unhappiness of all the teams according to BaoBao’s predictions.InputThere are multiple test cases. The first line of the input contains an integer TTT, indicating the number of test cases. For each test case:The first line contains three integers nnn, mmm and ppp (1≤n≤1051 \le n \le 10^51≤n≤105, n≤m≤109n \le m \le 10^9n≤m≤109, 1≤p≤1051 \le p \le 10^51≤p≤105), indicating the number of participating teams, the number of seats and the number of predictions.The second line contains nnn integers s1,s2,…,sns_1, s_2, \dots, s_ns1​,s2​,…,sn​ (1≤si≤m1 \le s_i \le m1≤si​≤m, and si≠sjs_i \ne s_jsi​​=sj​ for all i≠ji \ne ji​=j), indicating the seat number of each team.The following ppp lines each contains two integers aia_iai​ and bib_ibi​ (1≤ai≤n1 \le a_i \le n1≤ai​≤n, 1≤bi≤1091 \le b_i \le 10^91≤bi​≤109), indicating that the aia_iai​-th team solves a problem at time bib_ibi​ according to BaoBao’s predictions.It is guaranteed that neither the sum of nnn nor the sum of ppp over all test cases will exceed 5×1055 \times 10^55×105.OutputFor each test case output one integer, indicating the minimum total unhappiness of all the teams according to BaoBao’s predictions.Sample Input4
2 3 3
1 2
1 1
2 1
1 4
2 3 5
1 2
1 1
2 1
1 2
1 3
1 4
3 7 5
3 5 7
1 5
2 1
3 3
1 5
2 5
2 100 2
1 51
1 500
2 1000Sample Output1
4
5
50HintFor the first sample test case, if we choose the starting position to be the 1st seat, the total unhappiness will be (3-1) + (1-1) + (6-4) = 4. If we choose the 2nd seat, the total unhappiness will be (2-1) + (3-1) + (5-4) = 4. If we choose the 3rd seat, the total unhappiness will be (1-1) + (2-1) + (4-4) = 1. So the answer is 1.For the second sample test case, if we choose the starting position to be the 1st seat, the total unhappiness will be (3-1) + (1-1) + (3-2) + (3-3) + (6-4) = 5. If we choose the 2nd seat, the total unhappiness will be (2-1) + (3-1) + (2-2) + (5-3) + (5-4) = 6. If we choose the 3rd seat, the total unhappiness will be (1-1) + (2-1) + (4-2) + (4-3) + (4-4) = 4. So the answer is 4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
#define int long long
int n, m, p;
int Map[100005];

int Time[100005];

signed main() {
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	while (T--) {
		cin >> n >> m >> p;
		for (int i = 0; i < n; ++i) {
			cin >> Map[i];
			--Map[i];
		}
		for (int i = 0; i < p; ++i) {
			int x, y;
			cin >> x >> y;
			Time[i] = (Map[x - 1] - y % m + m) % m;
		}
		sort(Time, Time + p);
		int UnHappy = 0;
		for (int i = 1; i < p; ++i) {
			UnHappy += Time[i];
		}
		UnHappy -= Time[0] * (p - 1);

		int Ans = UnHappy;

		for (int i = 1; i < p; ++i) {
			UnHappy += m - p * (Time[i] - Time[i - 1]);
			Ans = min(Ans, UnHappy);
		}

		cout << Ans << endl;
	}
}