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