# F. Triangular Paths - Codeforces Round #710 (Div. 3)

https://codeforces.com/contest/1506/problem/F From the point (r1,c1) it is possible to reach the point (r2,c2), if there is a path between them only from activated edges. For example, in the picture above, there is a path from (1,1) to (3,2), but there is no path from (2,1) to (1,1).
Initially, you are at the point (1,1). For each turn, you can:
Replace activated edge for point (r,c). That is if the edge to the point (r+1,c) is activated, then instead of it, the edge to the point (r+1,c+1) becomes activated, otherwise if the edge to the point (r+1,c+1), then instead if it, the edge to the point (r+1,c) becomes activated. This action increases the cost of the path by 1;
Move from the current point to another by following the activated edge. This action does not increase the cost of the path.
You are given a sequence of n points of an infinite triangle (r1,c1),(r2,c2),…,(rn,cn). Find the minimum cost path from (1,1), passing through all n points in arbitrary order.

Then t test cases follow. Each test case begins with a line containing one integer n (1≤n≤2⋅105) is the number of points to visit. The second line contains n numbers r1,r2,…,rn (1≤ri≤109), where ri is the number of the layer in which i-th point is located.
The third line contains n numbers c1,c2,…,cn (1≤ci≤ri), where ci is the number of the i-th point in the ri layer.
It is guaranteed that all n points are distinct.It is guaranteed that there is always at least one way to traverse all n points.It is guaranteed that the sum of n over all test cases does not exceed 2⋅105.

``````#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<iostream>
#include<cstring>
using namespace std;
{
bool f=0; char _c=getchar(); _a=0;
while(_c<'0'||_c>'9'){ if(_c=='-') f=1; _c=getchar(); }
while(_c>='0'&&_c<='9'){ _a=(_a<<3)+(_a<<1)-'0'+_c; _c=getchar(); }
if(f) _a=-_a;
}

const int MAXN=200002;
int T,n,r[MAXN],c[MAXN],nowr,nowc,ans;
struct node
{
int r,c;
inline bool operator < (const node &x) const { return r<x.r; }
}e[MAXN];

int main()
{
{
sort(e+1,e+n+1);
nowr=1;
nowc=1;
ans=0;
for (int i=1;i<=n;++i)
{
if(e[i].r==nowr&&e[i].c==nowc) continue;
if(e[i].r==nowr+1)
{
if((nowr+nowc)&1)
{
if(e[i].c!=nowc+1) ++ans;
nowr=e[i].r;
nowc=e[i].c;
continue;
} else {
if(e[i].c!=nowc) ++ans;
nowr=e[i].r;
nowc=e[i].c;
continue;
}
}
int d1=e[i].r-nowr;
int d2=e[i].c-nowc;
if((nowr+nowc)&1)
{
int calc=(d1-d2+1)/2;
ans+=calc;
nowr=e[i].r;
nowc=e[i].c;
continue;
} else {
if(d1-1<d2)
{
ans+=d1;
nowr=e[i].r;
nowc=e[i].c;
} else {
int calc=(d1-d2)/2;
ans+=calc;
nowr=e[i].r;
nowc=e[i].c;
}
continue;
}
}
printf("%d\n",ans);
}
return 0;
}
``````