1506F - Triangular Paths - CodeForces Solution

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<numeric>
#include<unordered_map>
#include<cmath>
#include<queue>
#include<set>
// #include<memory>

#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long int;

struct DSU{
    vector<int> p, lvl;

    DSU(int n){
        p.resize(n);
        lvl.assign(n, 0);
        iota(all(p), 0);
    }

    int get(int i){
        if(i == p[i]) return i;
        return p[i] = get(p[i]);
    }

    bool unite(int a, int b){
        a = get(a);
        b = get(b);
        if(a == b){
            return false;
        }
        if(lvl[a] < lvl[b])swap(a, b);
        p[b] = a;
        if(lvl[a] == lvl[b]){
            ++lvl[a];
        }
        return true;
    }

    bool reachable(int a, int b){
        return get(a) == get(b);
    }
};


bool cmp(const pair<int,int>& A, const pair<int,int> &B){
    if(A.first < B.first) return true;
    else if(A.first == B.first) return A.second < B.second;
    else return false;
}

void DFS(int u, vector<vector<int>>& g, vector<int> &fin, vector<int> &vis, int &time){
    vis[u] = 1;
    for(auto k : g[u]){
        if(vis[k]==0) DFS(k,g,fin,vis,time);
    }
    fin[u] = time++;
}


void solve(){
    int n;
    cin >> n;
    vector<pair<int,int>> p(n+1);
    p[0] = make_pair(1,1);
    for(int i = 1; i<=n; i++){
        cin >> p[i].first;
    }
    for(int i = 1; i<=n; i++){
        cin >> p[i].second;
    }
    sort(all(p), cmp);
    int cost = 0;
    for(int i = 1; i<=n; i++){
        int x_1 = p[i-1].first;
        int y_1 = p[i-1].second;
        int x_2 = p[i].first;
        int y_2 = p[i].second;
        int m_1 = (x_1+y_1)%2;
        int m_2 = (x_2+y_2)%2;
        int r_1 = x_1 - y_1 + 1;
        int c_1 = y_1;
        int r_2 = x_2 - y_2 + 1;
        int c_2 = y_2;
        // cout << "printing actual " << x_1 << " " << y_1 << " " << x_2 << " " << y_2 << "\n";
        // cout << "printing proces " << r_1 << " " << c_1 << " " << r_2 << " " << c_2 << "\n";

        if(m_1==0 && m_2==0){
            if(r_1==r_2) cost+=(c_2-c_1);
            else cost+=((r_2-r_1)/2);      
        }
        else if(m_1==0 && m_2==1){
            cost+=((r_2-r_1)/2);
        }
        else if(m_1==1 && m_2==0){
            cost+=((r_2-r_1+1)/2);
        }
        else{
            cost+=((r_2-r_1)/2);
        }
    }
    cout << cost << "\n";

    
}


int main(){
    
    int t;
    cin >> t;
    while(t--){
        solve();
    }    


    return 0;
}