链接:https://codeforces.ml/contest/1324/problem/D
The next lecture in a high school requires two topics to be discussed. Theii-th topic is interesting byaiaiunits for the teacher and bybibiunits for the students.
The pair of topicsiiandjj(i<ji<j) is calledgoodifai+aj>bi+bjai+aj>bi+bj(i.e. it is more interesting for the teacher).
Your task is to find the number ofgoodpairs of topics.
Input
The first line of the input contains one integernn(2≤n≤2⋅1052≤n≤2⋅105) — the number of topics.
The second line of the input containsnnintegersa1,a2,…,ana1,a2,…,an(1≤ai≤1091≤ai≤109), whereaiaiis the interestingness of theii-th topic for the teacher.
The third line of the input containsnnintegersb1,b2,…,bnb1,b2,…,bn(1≤bi≤1091≤bi≤109), wherebibiis the interestingness of theii-th topic for the students.
Output
Print one integer — the number ofgoodpairs of topic.
Examples
input
Copy
54 8 2 6 24 5 4 1 3
output
Copy
7
input
Copy
41 3 2 41 3 2 4
output
Copy
0
代码:
#include<bits/stdc++.h>using namespace std;long long n,k,ans;long long a[200005],b[200005];vector<long long>c,d;int main(){cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=n;i++){cin>>b[i];a[i]-=b[i];}for(int i=1;i<=n;i++){if(a[i]>0)c.push_back(a[i]);elsed.push_back(a[i]);} sort(c.begin(),c.end());sort(d.rbegin(),d.rend());int j=0;ans=0;for(int i=0;i<c.size();i++) {while(j<d.size()&&c[i]+d[j]>0)j++;ans+=j;}ans+=((long long)c.size()*(c.size()-1))/2;cout<<ans<<endl;}