Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Social Distancing

By Shafin · Limits 1s, 512 MB

The country of KhoaNali is structured as a giant road with N(1N105)N (1 \leq N \leq 10^5) buildings on both sides, the northern buildings being houses and the southern buildings being workplaces. Each house has a unique label hi,(1hiN)h_i, (1 \leq h_i \leq N) and each workplace has a unique label wi,(1wiN)w_i, (1 \leq w_i \leq N)

Person x,(1xN)x, (1 \leq x \leq N) lives in house ii and goes to work at workplace jj if hi=wj=xh_i = w_j = x

Due to the recent NorocaVirus situation, everyone decided to distance himself from others. But due to the structure of KhoaNali, some of them may end up meeting someone else on their way. Your job is to find out the number of unordered pairs (i,j)(i, j) such that Person ii can meet Person jj on his way.


The first line contains an integer N(1N105)N (1 \leq N \leq 10^5) — the number of buildings on each side of the road.

Second line contains NN integers h1,h2,,hN h_1, h_2, \dots , h_N — labels of the houses.

Third line contains NN integers w1,w2,,wNw_1, w_2, \dots , w_N — labels of the workplaces.


Print a single integer — the number of unordered pairs (i,j)(i, j) such that Person ii and Person jj can meet on their way.


1 2 3 4
2 4 1 3

In the sample the pairs that can meet are (1,2),(1,4)(1, 2), (1, 4) and (3,4)(3, 4)



76% Solution Ratio

EgorKulikovEarliest, Apr '20

EgorKulikovFastest, 0.0s

kzvd4729Lightest, 1.3 MB

kzvd4729Shortest, 537B


Login to submit

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.