| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
upper_bound&lower_bound#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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator