Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## upper_bound&lower_bound

Posted by 1340502116 at 2016-07-17 19:55:12 on Problem 2785
```#include <iostream>
#include <algorithm>
using namespace std;
using namespace std;
const int MAXN=4005;
int A[MAXN],B[MAXN],C[MAXN],D[MAXN];
int E[16000005],top;
int n;
int upbound(int k)
{
int l=-1,r=top;
while(r-l>1)
{
int mid=(l+r)/2;
if(E[mid]<=k) l=mid;
else r=mid;
}
return r;
}
int lowbound(int k)
{
int l=-1,r=top;
while(r-l>1)
{
int mid=(l+r)/2;
if(E[mid]>=k)	r=mid;
else l=mid;
}
return r;
}
int main()
{
while(cin>>n)
{
top=0;
for(int i=0;i<n;i++)
{
cin>>A[i]>>B[i]>>C[i]>>D[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
E[top++]=A[i]+B[j];
}
}
sort(E,E+top);
int res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
int k=-(C[i]+D[j]);
int l=upbound(k)-lowbound(k);
res+=l;
}
}
cout<<res<<endl;
}
return 0;
}
```

Followed by: