Inconvenient Pairs codeforces solution

For Solution

Click Here!

There is a city that can be represented as a square grid with corner points in (0,0)(0,0) and (106,106)(106,106).

The city has nn vertical and mm horizontal streets that goes across the whole city, i. e. the ii-th vertical streets goes from (xi,0)(xi,0) to (xi,106)(xi,106) and the jj-th horizontal street goes from (0,yj)(0,yj) to (106,yj)(106,yj).

All streets are bidirectional. Borders of the city are streets as well.

There are kk persons staying on the streets: the pp-th person at point (xp,yp)(xp,yp) (so either xpxp equal to some xixi or ypyp equal to some yjyj, or both).

Let’s say that a pair of persons form an inconvenient pair if the shortest path from one person to another going only by streets is strictly greater than the Manhattan distance between them.

Calculate the number of inconvenient pairs of persons (pairs (x,y)(x,y) and (y,x)(y,x) are the same pair).

Let’s recall that Manhattan distance between points (x1,y1)(x1,y1) and (x2,y2)(x2,y2) is |x1x2|+|y1y2||x1−x2|+|y1−y2|.

Inconvenient Pairs solution codeforces

The first line contains a single integer tt (1t10001≤t≤1000) — the number of test cases.

The first line of each test case contains three integers nnmm and kk (2n,m21052≤n,m≤2⋅1052k31052≤k≤3⋅105) — the number of vertical and horizontal streets and the number of persons.

The second line of each test case contains nn integers x1,x2,,xnx1,x2,…,xn (0=x1<x2<<xn1<xn=1060=x1<x2<⋯<xn−1<xn=106) — the xx-coordinates of vertical streets.

The third line contains mm integers y1,y2,,ymy1,y2,…,ym (0=y1<y2<<ym1<ym=1060=y1<y2<⋯<ym−1<ym=106) — the yy-coordinates of horizontal streets.

Next kk lines contains description of people. The pp-th line contains two integers xpxp and ypyp (0xp,yp1060≤xp,yp≤106xp{x1,,xn}xp∈{x1,…,xn} or yp{y1,,ym}yp∈{y1,…,ym}) — the coordinates of the pp-th person. All points are distinct.

It guaranteed that sum of nn doesn’t exceed 21052⋅105, sum of mm doesn’t exceed 21052⋅105 and sum of kk doesn’t exceed 31053⋅105.

Inconvenient Pairs solution codeforces

For each test case, print the number of inconvenient pairs.



2 2 4
0 1000000
0 1000000
1 0
1000000 1
999999 1000000
0 999999
5 4 9
0 1 2 6 1000000
0 4 8 1000000
4 4
2 5
2 2
6 3
1000000 1
3 8
5 8
8 8
6 8



Inconvenient Pairs solution codeforces

The second test case is pictured below:

For example, points 33 and 44 form an inconvenient pair, since the shortest path between them (shown red and equal to 77) is greater than its Manhattan distance (equal to 55).

Points 33 and 55 also form an inconvenient pair: the shortest path equal to 10000011000001 (shown green) is greater than the Manhattan distance equal to 999999999999.

But points 55 and 99 don’t form an inconvenient pair, since the shortest path (shown purple) is equal to its Manhattan distance.

For Solution

Click Here!

Leave a Comment

Your email address will not be published.