分类： 赛事资讯

Farmer John's cows N are very particular about the room temperature in their barn. Some cows like the temperature to be on the cooler side, while others prefer more warmth.

Farmer John's barn contains a sequence of N stalls, numbered 1…N, each containing a single cow. The i-th cow prefers the temperature of her stall to be pi, and right now the temperature in her stall is ti. In order to make sure every cow is comfortable, Farmer John installs a new air conditioning system that is controlled in a somewhat interesting way. He can send commands to the system telling it to either raise or lower the temperature in a consecutive series of stalls by 1 unit --- for example "raise the temperature in stalls 5…8 by 1 unit". The series of stalls could be as short as just a single stall.

Please help Farmer John determine the minimum number of commands he needs to send his new air conditioning system so that every cow's stall is at the ideal temperature for its resident cow.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains N. The next line contains the N non-negative integers p1…pN, separated by spaces. The final line contains the N non-negative integers t1…tN.

OUTPUT FORMAT (print output to the terminal / stdout):

Please write a single integer as output containing the minimum number of commands Farmer John needs to use.

SAMPLE INPUT:

5

1 5 3 3 4

1 2 2 2 1

SAMPLE OUTPUT:

5

One optimal set of commands Farmer John can use might be the following:

Initial temperatures: 1 2 2 2 1

Increase stalls 2..5: 1 3 3 3 2

Increase stalls 2..5: 1 4 4 4 3

Increase stalls 2..5: 1 5 5 5 4

Decrease stalls 3..4: 1 5 4 4 4

Decrease stalls 3..4: 1 5 3 3 4

SCORING:

Test cases 2-5 satisfy N≤100.

Test cases 6-8 satisfy N≤1000.

Test cases 9-10 satisfy N≤100,000.

In test cases 1-6 and 9, temperature values are at most 100.

In test cases 7-8 and 10, temperature values are at most 10,000.

Farmer John has recently acquired N new cows (3≤N≤5×10^5), each of whose breed is either Guernsey or Holstein.

The cows are currently standing in a line, and Farmer John wants take a photo of every sequence of three or more consecutive cows. However, he doesn't want to take a photo in which there is exactly one cow whose breed is Guernsey or exactly one cow whose breed is Holstein --- he reckons this singular cow would feel isolated and self-conscious. After taking a photo of every sequence of three or more cows, he throws out all of these so-called "lonely" photos, in which there is exactly one Guernsey or exactly one Holstein.

Given the lineup of cows, please help Farmer John determine how many lonely photos he will throw out. Two photos are different if they start or end at different cows in the lineup.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains N.

The second line contains a string of N characters. The ith character is G if the ith cow in the line is a Guernsey. Otherwise, it will be an H and the ith cow is a Holstein.

OUTPUT FORMAT (print output to the terminal / stdout):

Please print the number of photos Farmer John will throw out because they are lonely.

SAMPLE INPUT:

5

GHGHG

SAMPLE OUTPUT:

3

Every substring of length 3 in this example contains exactly one cow whose breed is Guernsey or exactly one cow whose breed is Holstein --- so these substrings represent lonely photos and would be thrown out by Farmer John. All longer substrings (GHGH, HGHG, and GHGHG) are acceptable to him.

SCORING:

Test cases 2 through 4 have N≤50.

Test cases 5 through 10 have N≤5000.

For a bit more challenge, test case 11 has no other constraints. Note that the answer for this case might be too large to fit into a standard 32-bit integer, and might require use of larger integer types (e.g., a 64-bit "long long int" type in C++).

The cows are hard at work trying to invent interesting new games to play. One of their current endeavors involves a set of N intervals (1≤N≤2·10^5), where the ith interval starts at position ai on the number line and ends at position bi≥ai. Both ai and bi are integers in the range 0…M, where 1≤M≤5000.

To play the game, Bessie chooses some interval (say, the ith interval) and her cousin Elsie chooses some interval (say, the jth interval, possibly the same as Bessie's interval). Given some value k, they win if ai+aj≤k≤bi+bj.

For every value of k in the range 0…2M, please count the number of ordered pairs (i,j) for which Bessie and Elsie can win the game.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains N and M. Each of the next N lines describes an interval in terms of integers ai and bi.

OUTPUT FORMAT (print output to the terminal / stdout):

Please print 2M+1 lines as output, one for each value of k in the range 0…2M.

SAMPLE INPUT:

2 5

1 3

2 5

SAMPLE OUTPUT:

0

0

1

3

4

4

4

3

3

1

1

In this example, for just k=3, there are three ordered pairs that will allow Bessie and Elie to win: (1,1), (1,2), and (2,1).

SCORING:

Test cases 1-2 satisfy N≤100,M≤100.

Test cases 3-5 satisfy N≤5000.

Test cases 6-20 satisfy no additional constraints.

Note that output values might be too large to fit into a 32-bit integer, so you may want to use 64-bit integers (e.g., "long long" ints in C or C++).

Farmer John's farm consists of a set of N fields (1≤N≤10^5), conveniently numbered 1…N. Between these fields are M bi-directed paths (0≤M≤10^5), each connecting a pair of fields.

The farm contains two barns, one in field 1 and the other in field N. Farmer John would like to ensure that there is a way to walk between the two barns along some series of paths. He is willing to build up to two new paths to accomplish this goal. Due to the way the fields are situated, the cost of building a new path between fields i and j is (i−j)2.

Please help Farmer John determine the minimum cost needed such that barns 1 and N become reachable from each-other.

INPUT FORMAT (input arrives from the terminal / stdin):

Each input test case contains T sub-cases (1≤T≤20), all of which must be solved correctly to solve the input case.

The first line of input contains T, after which T sub-test cases follow.

Each sub-test case starts with two integers, N and M. Next, M lines follow, each one containing two integers i and j, indicating a path between two different fields i and j. It is guaranteed that there is at most one path between any two fields, and that the sum of N+M over all sub-test cases is at most 5·10^5.

OUTPUT FORMAT (print output to the terminal / stdout):

Output T lines. The ith line should contain a single integer giving the minimum cost for the ith sub-test case.

SAMPLE INPUT:

2

5 2

1 2

4 5

5 3

1 2

2 3

4 5

SAMPLE OUTPUT:

2

1

In the first sub-test case, it is optimal to connect fields 2 and 3 with a path, and fields 3 and 4 with a path.

In the second sub-test case, it is optimal to connect fields 3 and 4 with a path. No second path is needed.

SCORING:

Test case 2 satisfies N≤20.

Test cases 3-5 satisfy N≤10^3.

Test cases 6-10 satisfy no additional constraints.

Farmer John owns a long farm along the highway that can be considered somewhat like a one-dimensional number line. Along the farm, there are K grassy patches (1≤K≤2·10^5); the i-th patch is located at position pi and has an associated tastiness value ti (0≤ti≤109). Farmer John's nemesis, Farmer Nhoj, has already situated his M cows (1≤M≤2·10^5) at locations f1…fM. All K+M of these locations are distinct integers in the range [0,10^9].
Farmer John needs to pick N (1≤N≤2·10^5) locations (not necessarily integers) for his cows to be located. These must be distinct from those already occupied by the cows of Farmer Nhoj, but it is possible for Farmer John to place his cows at the same locations as grassy patches.

Whichever farmer owns a cow closest to a grassy patch can claim ownership of that patch. If there are two cows from rival farmers equally close to the patch, then Farmer Nhoj claims the patch.

Given the locations of Farmer Nhoj's cows and the locations and tastiness values of the grassy patches, determine the maximum total tastiness Farmer John's cows can claim if optimally positioned.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains K, M, and N.
The next K lines each contain two space-separated integers pi and ti.

The next M lines each contain a single integer fi.

OUTPUT FORMAT (print output to the terminal / stdout):
An integer denoting the maximum total tastiness. Note that the answer to this problem can be too large to fit into a 32-bit integer, so you probably want to use 64-bit integers (e.g., "long long"s in C or C++).
SAMPLE INPUT:
6 5 2
0 4
4 6
8 10
10 8
12 12
13 14
2
3
5
7
11
SAMPLE OUTPUT:
36
If Farmer John places cows at positions 11.5 and 8 then he can claim a total tastiness of 10+12+14=36.

Problem credits: Brian Dean

Bessie the cow enjoys arts and crafts. In her free time, she has made N (1≤N≤50) bracelets, conveniently numbered 1…N. The ith bracelet is painted color i out of a set of N different colors. After constructing the bracelets, Bessie placed them on a table for display (which we can think of as the 2D plane). She was careful to arrange the bracelets to satisfy the following three conditions:

Every bracelet was a single closed polygonal chain -- a series of vertices (points) connected sequentially by line segments, where the first and last points are the same (Feel welcome to consult the wikipedia page for more detail: polygonal chain),

No bracelet intersected itself (this corresponds to a "simple" polygonal chain); and

No two bracelets intersected.

Unfortunately, right after Bessie arranged the bracelets in such a careful manner, Farmer John drove by in his tractor, shaking the table and causing the bracelets to shift around and possibly break into multiple (not necessarily closed or simple) polygonal chains! Afterward, Bessie wanted to check whether the three conditions above still held. However, it was dark, so she couldn't see the bracelets anymore.

Fortunately, Bessie had a flashlight. She chose M (1≤M≤50) vertical lines x=1,x=2,…,x=M and for each line, she swept the beam of the flashlight along that line from y=?∞ to y=∞, recording the colors of all bracelets she saw in the order they appeared. Luckily, no beam crossed over any vertex of any polygonal chain or two line segments at the same time. Furthermore, for each beam, every color that appeared appeared exactly twice.

Can you help Bessie use this information to determine whether it is possible that the bracelets still satisfy all three of the conditions above?

INPUT FORMAT (input arrives from the terminal / stdin):

Each input case contains T sub-cases (1≤T≤50) that must all solved independently to solve the full input case. Consecutive test cases are separated by newlines.

The first line of the input contains T. Each of the T sub-test cases then follow.

The first line of each sub-test case contains two integers N and M. Each sub-test case then contains M additional lines. For each i from 1 to M, the i-th additional line contains an integer ki (0≤ki≤2N, ki even), followed by ki integers ci1,ci2,…,ciki (cij∈[1,N], every cij appears zero or two times). This means that when Bessie swept her flashlight from (i,?∞) to (i,∞), she encountered the colors ci1,ci2,…,ciki in that order.

OUTPUT FORMAT (print output to the terminal / stdout):

For each sub-test case, print YES if it is possible for the three conditions above to be satisfied. Otherwise, print NO.

SAMPLE INPUT:

5

1 2

2 1 1

2 1 1

1 3

2 1 1

0

2 1 1

2 1

4 1 2 1 2

4 2

6 1 2 2 3 3 1

6 1 2 4 4 2 1

2 2

4 1 1 2 2

4 2 2 1 1

SAMPLE OUTPUT:

YES

NO

NO

YES

NO

An example of a feasible bracelet configuration for the first sub-case is:

For the fourth sub-case, a feasible arrangement is the following:

SCORING:

Test case 2 satisfies N=1.

Test cases 3-5 satisfy N=2.

Test cases 6-8 satisfy M=1.

Test cases 9-14 satisfy M=2.

Test cases 15-20 satisfy no additional constraints.

Bessie knows a number x+0.5 where x is some integer between 0 to N, inclusive (1≤N≤2·10^5).

Elsie is trying to guess this number. She can ask questions of the form "is i high or low?" for some integer i between 1 and N, inclusive. Bessie responds by saying "HI" if i is greater than x+0.5, or "LO" if i is less than x+0.5.

Elsie comes up with the following strategy for guessing Bessie's number. Before making any guesses, she creates a list of N numbers, where every number from 1 to N occurs exactly once (in other words, the list is a permutation of size N). Then she goes through the list, guessing numbers that appear in the list in order.

However, Elsie skips any unnecessary guesses. That is, if Elsie is about to guess some number i and Elsie previously guessed some j<i and Bessie responded with "HI", Elsie will not guess i and will move on to the next number in the list. Similarly, if she is about to guess some number i and she previously guessed some j>i and Bessie responded with "LO", Elsie will not guess i and will move on to the next number in the list. It can be proven that using this strategy, Elsie always uniquely determines x regardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a single string S, then the number of times Bessie says "HILO" is the number of length 4 substrings of S that are equal to "HILO."

Bessie knows that Elsie will use this strategy; furthermore, she also knows the exact permutation that Elsie will use. However, Bessie has not decided on what value of x to choose.

Help Bessie determine how many times she will say "HILO" for each value of x.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N.

The second line contains Elsie's permutation of size N.

OUTPUT FORMAT (print output to the terminal / stdout):

For each x from 0 to N, inclusive, output the number of times Bessie will say HILO on a new line.

SAMPLE INPUT:

5

5 1 2 4 3

SAMPLE OUTPUT:

0

1

1

2

1

0

For x=0, Bessie will say "HIHI," for a total of zero "HILO"s.

For x=2, Bessie will say "HILOLOHIHI," for a total of one "HILO".

For x=3, Bessie will say "HILOLOHILO", for a total of two "HILO"s.

SCORING:

Tests 1 to 4 satisfy N≤5000.

Tests 5 to 8 have a uniformly random permutation.

Tests 9 to 20 satisfy no further constraints.

There are a total of N (1≤N≤10^5) cows on the number line. The location of the i-th cow is given by xi (0≤xi≤10^9), and the weight of the i-th cow is given by yi (1≤yi≤10^4).

At Farmer John's signal, some of the cows will form pairs such that

Every pair consists of two distinct cows a and b whose locations are within K of each other (1≤K≤10^9); that is, |xa?xb|≤K.

Every cow is either part of a single pair or not part of a pair.

The pairing is maximal; that is, no two unpaired cows can form a pair.

It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically,

If T=1, compute the minimum possible sum of weights of the unpaired cows.

If T=2, compute the maximum possible sum of weights of the unpaired cows.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains T, N, and K.

In each of the following N lines, the i-th contains xi and yi. It is guaranteed that 0≤x1<x2<?<xN≤10^9.

OUTPUT FORMAT (print output to the terminal / stdout):

Please print out the minimum or maximum possible sum of weights of the unpaired cows.

SAMPLE INPUT:

2 5 2

1 2

3 2

4 2

5 1

7 2

SAMPLE OUTPUT:

6

In this example, cows 2 and 4 can pair up because they are at distance 2, which is at most K=2. This pairing is maximal, because cows 1 and 3 are at distance 3, cows 3 and 5 are at distance 3, and cows 1 and 5 are at distance 6, all of which are more than K=2. The sum of weights of unpaired cows is 2+2+2=6.

SAMPLE INPUT:

1 5 2

1 2

3 2

4 2

5 1

7 2

SAMPLE OUTPUT:

2

Here, cows 1 and 2 can pair up because they are at distance 2≤K=2, and cows 4 and 5 can pair up because they are at distance 2≤K=2. This pairing is maximal because only cow 3 remains. The weight of the only unpaired cow here is simply 2.

SAMPLE INPUT:

2 15 7

3 693

10 196

12 182

14 22

15 587

31 773

38 458

39 58

40 583

41 992

84 565

86 897

92 197

96 146

99 785

SAMPLE OUTPUT:

2470

The answer for this example is 693+992+785=2470.

SCORING:

Test cases 4-8 satisfy T=1.

Test cases 9-14 satisfy T=2 and N≤5000.

Test cases 15-20 satisfy T=2.

Problem credits: Benjamin Qi

Bessie knows a number x+0.5 where x is some integer between 0 to N, inclusive (1≤N≤5000).

Elsie is trying to guess this number. She can ask questions of the form "is i high or low?" for some integer i between 1 and N, inclusive. Bessie responds by saying "HI!" if i is greater than x+0.5, or "LO!" if i is less than x+0.5.

Elsie comes up with the following strategy for guessing Bessie's number. Before making any guesses, she creates a list of N numbers, where every number from 1 to N occurs exactly once (in other words, the list is a permutation of size N.) Then, she goes through the list, guessing numbers that appear in the list in order. However, Elsie skips any unnecessary guesses. That is, if Elsie is about to guess some number i and Elsie previously guessed some j<i such that Bessie responded with "HI!," Elsie will not guess i and will move on to the next number in the list. Similarly, if she is about to guess some number i and she previously guessed some j>i such that Bessie responded with "LO!," Elsie will not guess i and will move on to the next number in the list. It can be proven that using this strategy, Elsie always uniquely determines x regardless of the permutation she creates.

If we concatenate all of Bessie's responses of either "HI" or "LO" into a single string S, the number of times Bessie says "HILO" is the number of length 4 substrings of S that are equal to "HILO."

Bessie knows that Elsie will use this strategy and has already chosen the value of x, but she does not know what permutation Elsie will use. Your goal is to compute the sum of the number of times Bessie says "HILO" over all permutations that Elsie could possibly choose, modulo 10^9+7.

INPUT FORMAT (input arrives from the terminal / stdin):

The only line of input contains N and x.

OUTPUT FORMAT (print output to the terminal / stdout):

The total number of HILOs modulo 10^9+7.

SAMPLE INPUT:

4 2

SAMPLE OUTPUT:

17

In this test case, Bessie's number is 2.5.

For example, if Elsie's permutation is (4,1,3,2), then Bessie will say "HILOHILO," for a total of two "HILO"s. As another example, if Elsie's permutation is (3,1,2,4), then Bessie will say "HILOLO," for a total of one "HILO."

SAMPLE INPUT:

60 10

SAMPLE OUTPUT:

508859913

Make sure to output the sum modulo 10^9+7.

SCORING:

Test cases 3-10 satisfy N≤50.

Test cases 11-18 satisfy N≤500.

Test cases 19-26 satisfy no additional constraints.

There are a total of N (1≤N≤5000) cows on the number line, each of which is a Holstein or a Guernsey. The breed of the i-th cow is given by bi∈{H,G}, the location of the i-th cow is given by xi (0≤xi≤10^9), and the weight of the i-th cow is given by yi (1≤yi≤10^5).
At Farmer John's signal, some of the cows will form pairs such that
Every pair consists of a Holstein h and a Guernsey g whose locations are within K of each other (1≤K≤10^9); that is, |xh?xg|≤K.
Every cow is either part of a single pair or not part of a pair.
The pairing is maximal; that is, no two unpaired cows can form a pair.
It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically,
If T=1, compute the minimum possible sum of weights of the unpaired cows.
If T=2, compute the maximum possible sum of weights of the unpaired cows.
INPUT FORMAT (input arrives from the terminal / stdin):
The first input line contains T, N, and K.
Following this are N lines, the i-th of which contains bi,xi,yi. It is guaranteed that 0≤x1<x2<?<xN≤10^9.
OUTPUT FORMAT (print output to the terminal / stdout):
The minimum or maximum possible sum of weights of the unpaired cows.
SAMPLE INPUT:
2 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
SAMPLE OUTPUT:
16
Cows 2 and 3 can pair up because they are at distance 1, which is at most K=4. This pairing is maximal, because cow 1, the only remaining Guernsey, is at distance 5 from cow 4 and distance 7 from cow 5, which are more than K=4. The sum of weights of unpaired cows is 1+6+9=16.
SAMPLE INPUT:
1 5 4
G 1 1
H 3 4
G 4 2
H 6 6
H 8 9
SAMPLE OUTPUT:
6
Cows 1 and 2 can pair up because they are at distance 2≤K=4, and cows 3 and 5 can pair up because they are at distance 4≤K=4. This pairing is maximal because only cow 4 remains. The sum of weights of unpaired cows is the weight of the only unpaired cow, which is simply 6.
SAMPLE INPUT:
2 10 76
H 1 18
H 18 465
H 25 278
H 30 291
H 36 202
G 45 96
G 60 375
G 93 941
G 96 870
G 98 540
SAMPLE OUTPUT:
1893
The answer to this example is 18+465+870+540=1893.
SCORING:
Test cases 4-7 satisfy T=1.
Test cases 8-14 satisfy T=2 and N≤300.
Test cases 15-22 satisfy T=2.
**Note: the memory limit for this problem is 512MB, twice the default.**