Time Limit: 1000MS | Memory Limit: 30000K | |
Total Submissions: 7077 | Accepted: 3181 |
Description
Each cow i has an associated "hearing" threshold v(i) (in the range
1..20,000). If a cow moos to cow i, she must use a volume of at least
v(i) times the distance between the two cows in order to be heard by cow
i. If two cows i and j wish to converse, they must speak at a volume
level equal to the distance between them times max(v(i),v(j)).
Suppose each of the N cows is standing in a straight line (each cow
at some unique x coordinate in the range 1..20,000), and every pair of
cows is carrying on a conversation using the smallest possible volume.
Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows.
Input
* Lines 2..N+1: Two integers: the volume threshold and x coordinate
for a cow. Line 2 represents the first cow; line 3 represents the
second cow; and so on. No two cows will stand at the same location.
Output
Sample Input
4
3 1
2 5
2 6
4 3
Sample Output
57
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
typedef long long ll;
using namespace std;
const int N = 2e4+;
const int M = ;
const int mod=1e9+;
ll tree[][N];
int n,m;
struct man{
int x,v;
bool operator< (const man &it)const{
return v<it.v;
}
}a[N];
void add(int k,int num){
while(k<=){
tree[][k]+=num;
tree[][k]+=;
k+=k&(-k);
}
}
ll Sum(int k,int d){
ll sum=;
while(k>){
sum+=tree[d][k];
k-=k&(-k);
}
return sum;
}
int main() {
scanf("%d",&n);
int v,x;
for(int i=;i<=n;i++){
scanf("%d%d",&a[i].v,&a[i].x);
}
sort(a+,a++n);
ll ans=;
for(int i=;i<=n;i++){
ll sump=Sum(a[i].x,);
ll sumx=Sum(a[i].x,);
ans+=a[i].v*(sump*a[i].x-sumx)+a[i].v*(Sum(,)-sumx-(i--sump)*a[i].x);
add(a[i].x,a[i].x);
}
printf("%lld\n",ans);
return ;
}