ACDream - Sum

 1 /*
 2 * this code is made by sineatos
 3 * Problem: 1174
 4 * Verdict: Accepted
 5 * Submission Date: 2014-08-01 12:08:56
 6 * Time: 2488MS
 7 * Memory: 3240KB
 8 */
 9 #include <cstdio>
10 #include <cstring>
11 #include <utility>
12 #include <algorithm>
13 #define MAX 50002
14 #define ll long long
15 using namespace std;
16  
17 typedef pair<int,int> pii;
18  
19 pii a[MAX],b[MAX];
20 int n,m;
21 ll sumb[MAX],sumbj[MAX],sumj[MAX];
22 int loc[MAX];
23  
24 inline ll Sum(int i,int r,int l){
25     ll sum=0;
26     sum=(ll)a[i].first*a[i].second*(r+1-l) - (ll)a[i].first*(sumj[r]-sumj[l-1]) -(ll)a[i].second*(sumb[r]-sumb[l-1]) + (sumbj[r]-sumbj[l-1]);
27     return sum;
28 }
29  
30 int main()
31 {
32     ll sum;
33     //freopen("data.txt","r",stdin);
34     while(scanf("%d %d",&n,&m)!=EOF){
35         for(int i=1;i<=n;i++){
36             scanf("%d",&a[i].first);
37             a[i].second=i;
38         }
39         for(int i=1;i<=m;i++){
40             scanf("%d",&b[i].first);
41             b[i].second=i;
42         }
43         sort(a+1,a+n+1);
44         sort(b+1,b+m+1);
45         sumb[0]=sumbj[0]=sumj[0]=0;
46         int k=1;
47         for(int i=1;i<=n;i++){
48             while(k<=m && a[i].first>=b[k].first) k++;
49             loc[i]=k;
50         }
51         for(int i=1;i<=m;i++){
52             sumb[i]=sumb[i-1]+b[i].first;
53             sumbj[i]=sumbj[i-1]+(ll)b[i].first*b[i].second;
54             sumj[i]=sumj[i-1]+b[i].second;
55         }
56         sum=0;
57         for(int i=1;i<=n;i++){
58             int mid=loc[i];
59             ll p1=Sum(i,m,mid);
60             ll p2=Sum(i,mid-1,1);
61             sum+=p2-p1;
62         }
63         printf("%lld\n",sum);
64     }
65     return 0;
66 }