Untitled

 avatar
unknown
plain_text
a year ago
1.3 kB
9
Indexable
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef vector<ll> vl;

void solve()
{
    ll i, j, n, cnt = 0;
    cin >> n;
    vl A(n), B(n), C(n);
    for (i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    for (i = 0; i < n; i++)
    {
        cin >> B[i];
    }
    for (i = 0; i < n; i++)
    {
        C[i] = A[i] - B[i];
    }
    // since addition is commutative just sort the elements of the array C
    sort(C.begin(), C.end());
    for (i = 0; i < n; i++)
    {
        if (C[i] <= 0)
        {
            // we want to find element Cj which is strictly greater than -Ci
            // Cj>-Ci equivalent to finding a  Cj>=-Ci+1
            if (lower_bound(C.begin(), C.end(), -C[i] + 1ll) - C.begin() != n)
            {
                cnt += n - (lower_bound(C.begin(), C.end(), -C[i] + 1ll) - C.begin());
            }
        }
        else
        {
            cnt += n - (i + 1);
        }
    }
    cout << cnt << endl;
}

int main()
{
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    // #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int i, T;

    T = 1;
    cin >> T;

    for (i = 1; i <= T; i++)
    {
        solve();
    }
    return 0;
}
Editor is loading...
Leave a Comment