Direct Connections

                            Solution in C :

In C ++ :





#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string>
#include <string.h>
#define pb push_back
#define mp make_pair
#define SS(a,b) scanf("%d%d",&a,&b);
#define S(a) scanf("%d",&a);
#define SSL(a,b) scanf("%lld%lld",&a,&b);
#define SL(a) scanf("%lld",&a);
#define SSS(a,b,c) scanf("%d %d %d",&a,&b,&c);
#define GI ({int t;scanf("%d",&t);t;})
#define GL ({ll t;scanf("%lld",&t);t;})
#define MAXN 500000
#define FOR(i,a,n) for(int i=a;i<n;i++)
#define REP(i,n) FOR(i,0,n)
#define INPUT freopen("input.txt","r",stdin);
#define OUTPUT freopen("output1.txt","w",stdout);
#define disvec(v) { for(int vec_index=0;vec_index<v.size();vec_index++) cout<<v[vec_index]<<" "; cout<<endl;}
using namespace std;
typedef  long long LL;
typedef  long long ll;
pair<LL,LL>input[200100];
map<LL,int>m;
LL DistBIT[200100];
LL SumBIT[200100];
LL MOD=1000000007LL;
int maxval=200010;
void init(){
	REP(i,200100)DistBIT[i]=SumBIT[i]=0;
}
void update_Dist(int idx,LL val){
	while(idx<=maxval){
		DistBIT[idx]=(DistBIT[idx]+val);
        idx+=(idx & -idx);              
	}
}
void update_Sum(int idx,LL val){
	while(idx<=maxval){
		SumBIT[idx]=(SumBIT[idx]+val)%MOD;
		idx+=(idx & -idx);              		
	}
}
LL query_cnt(int idx){
	LL res=0;
	while(idx>0){
		res=(res+SumBIT[idx]);
		idx-=(idx & -idx);
	}
	return res;
}
LL QUERY_cnt(int start,int end){
	if(start>end)return 0;
	return (query_cnt(end)-query_cnt(start-1));
}
LL query_Dist(int idx){
	LL res=0;
	while(idx>0){
		res=(res+DistBIT[idx]);
		idx-=(idx & -idx);
	}
	return res;
}
LL QUERY_Dist(int start, int end){
	if(start>end)return 0;
	return (query_Dist(end)-query_Dist(start-1));
}
pair<LL,LL>Mapp[200100];
int main(){
	int t=GI;
	while(t--){
		init();
		int n=GI;
		m.clear();
		REP(i,n){scanf("%lld",&input[i].second);}
		REP(i,n){scanf("%lld",&input[i].first);}
		REP(i,n){
			Mapp[i].first=input[i].second;
			Mapp[i].second=input[i].first;
		}
		sort(Mapp,Mapp+n);
		int total=2;
		REP(i,n)m[Mapp[i].first]=total,total++;
		
		sort(input,input+n);
		
		LL ans=0;
		update_Dist(m[input[0].second],input[0].second);
		update_Sum(m[input[0].second],1);
		for(int i=1;i<n;i++){
			LL xi=input[i].second;
			LL curmapped=m[input[i].second];
			
			LL Leftcnt=QUERY_cnt(1,curmapped-1);
			LL Rightcnt=QUERY_cnt(curmapped+1,total+2);
			
			LL LeftDist=QUERY_Dist(1,curmapped-1);
			LL RightDist=QUERY_Dist(curmapped+1,total+2);
			
			LL Tempans=xi*(Leftcnt-Rightcnt);
			
			Tempans-=LeftDist;
			Tempans+=RightDist;
			Tempans=(Tempans*input[i].first)%MOD;

			ans=(ans+Tempans)%MOD;
			update_Dist(curmapped,xi);
			update_Sum(curmapped,1);
		}
		cout<<(ans+MOD)%MOD<<endl;
	}
    GI;
    return 0;
}









In Java :






import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;


public class DirectConnection {
    static final class IO {
        //Standard IO
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = null;

        static int ni() {
            return Integer.parseInt(ns());
        }

        static long nl() {
            return Long.parseLong(ns());
        }

        static double nd() {
            return Double.parseDouble(ns());
        }

        static String ns() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                }
            }
            return tokenizer.nextToken();
        }

        static String nline() {
            tokenizer = null;
            String ret = null;
            try {
                ret = br.readLine();
            } finally {
                return ret;
            }
        }
    }


    static final class City {
        int i;
        int cordinate;
        int cable;
    }

    static class FenwickTree {
        static long MOD = 1000000000 + 7;

        public static void update(long[] arr, int pos, int val)
        {
            int len = arr.length;
            for (; pos < len; pos |= (pos + 1))
                arr[pos] = (arr[pos] + val + MOD) % MOD;
        }

        /** Function to query **/
        public static long query(long[] arr, int pos)
        {
            long sum = 0;
            for (; pos >= 0; pos = (pos & (pos + 1)) - 1)
                sum = (arr[pos] + sum + MOD) % MOD;

            return sum;
        }
    }

    static long f(City[] cityCor) {
        Arrays.sort(cityCor, new Comparator<City>() {
            @Override
            public int compare(City o1, City o2) {
                return Integer.compare(o1.cordinate, o2.cordinate);
            }
        });
        long[] iList = new long[cityCor.length];
        long[] cord = new long[cityCor.length];
        long[] cable = new long[cityCor.length];
        for (int i = 0; i < cityCor.length; i++) {
            cityCor[i].i = i;
            FenwickTree.update(cord, i, cityCor[i].cordinate);
            FenwickTree.update(cable, i, cityCor[i].cable);
            FenwickTree.update(iList, i, 1);
        }
        Arrays.sort(cityCor, new Comparator<City>() {
            @Override
            public int compare(City o1, City o2) {
                return Integer.compare(o2.cable, o1.cable);
            }
        });
        long sum = 0;
        for (City c : cityCor) {
            sum = (sum + g(c, iList, cord)) % FenwickTree.MOD;
            //System.out.println(c.cable + "--" + sum);
            FenwickTree.update(iList, c.i, -1);
            FenwickTree.update(cord, c.i, -1 * c.cordinate);

        }
        return sum;
    }

    private static long g(City c, long[] iList, long[] cord) {
        long MOD = FenwickTree.MOD;
        int i = c.i;
        long l = FenwickTree.query(cord, i);
        long n = FenwickTree.query(cord, cord.length - 1);
        n = (n - l + FenwickTree.MOD) % FenwickTree.MOD;
        //System.out.println(i + "&& " + l + "." + n);
        long li = FenwickTree.query(iList, i);
        long ni = FenwickTree.query(iList, iList.length - 1);
        ni = (ni - li + FenwickTree.MOD) % FenwickTree.MOD;
        //System.out.println(i + "|| " + li + "." + ni);

        long cc = (((c.cordinate * li - l + MOD) % MOD) * c.cable) % MOD;
        long nn = (((n - c.cordinate * ni + MOD) % MOD) * c.cable) % MOD;
        return (cc + nn) % MOD;
    }
    public static void main(String[] argv) {
        int T = IO.ni();
        for (int t = 0; t < T; t++) {
            int N = IO.ni();
            City[] citArr = new City[N];

            for (int i = 0; i < N; i++) {
                citArr[i] = new City();
                citArr[i].cordinate = IO.ni();
            }
            for (int i = 0; i < N; i++) {
                citArr[i].cable = IO.ni();

            }
            System.out.println(f(citArr));
        }
    }
}








In C :





#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
struct node {
    long int c, p;
};
struct node a[200000];
#define MOD(x) ((x) < 0 ? -(x) : (x))
#define MODULO(x) ((x) > 1000000007 ? (x) % 1000000007 : (x))
int cmp(void *a, void *b)
{
    return ((struct node *)b)->p - ((struct node *)a)->p;
}
int main() {
    long int n, t, i, j, tot, ans;
    scanf("%ld", &t);
    while (t--) {
        scanf("%ld", &n);
        tot = 0;
        for(i = 0; i < n; i++) {
            scanf("%ld", &a[i].c);
            //tot += c;
        }
        for(i = 0; i < n; i++) {
            scanf("%ld", &a[i].p);
        }
        qsort(a, n, sizeof(a[0]), (__compar_fn_t)cmp);
        ans = 0;
        for(i = 0; i < n; i++) {
            tot = 0;
            for(j = i+1; j < n; j++)
                tot += MOD(a[j].c - a[i].c);
            ans += MODULO(tot) * MODULO(a[i].p);
            ans = MODULO(ans);
        }
        printf("%ld\n", ans);
        
    }
    return 0;
}








In Python3 :







class fenpiece:
    __slots__ = ['x','p','px','c']
    def __init__(self,x=0,p=0,px=0,c=0):
        self.x = x
        self.p = p
        self.px = px
        self.c = c
    def __iadd__(self,other):
        self.x += other.x
        self.p += other.p
        self.px += other.px
        self.c += other.c
        return self
    def __radd__(self,other):
        return fenpiece(self.x,self.p,self.px,self.c)
    def __sub__(self,other):
        return fenpiece(self.x-other.x,self.p-other.p,self.px-other.px,self.c-other.c)
        
def fensum(seq,i):
    sum = 0
    while i:
        sum += seq[i-1]
        i -= i&-i
    return sum

def fensumrange(seq,i,j):
    return fensum(seq,j) - fensum(seq,i)

def fenadd(seq,i,v):
    i += 1
    bound = len(seq) + 1
    while i < bound:
        seq[i-1] += v
        i += i&-i
        
pBound = 10001
magicmod = 1000000007
fenlist = [fenpiece() for i in range(pBound)]
T = int(input())
for t in range(T):
    total = 0
    N = int(input())
    X = [int(s) for s in input().split()]
    P = [int(s) for s in input().split()]
    cities = sorted(zip(X,P))
    cable = 0
    for x,p in cities:
        underP = fensum(fenlist,p)
        overP = fensumrange(fenlist,p,pBound)
        cable =  (cable + p*(underP.c*x - underP.x) + overP.p*x - overP.px)%magicmod
        fenadd(fenlist,p,fenpiece(x,p,x*p,1))
    print(cable)
    for f in fenlist:f.__init__()