2387.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2387 on 2006-09-28 at 16:23:20 */
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long int64;
typedef pair<int64, int64> pii;
const int N = 20480;

class TreeArray {
private:
	int c, a[N], xc[N];
	int lowBit(int t) const { return t&(-t); }
public:
	void clear(int nc) { c = nc+1; memset(a, 0, sizeof(a)); memset(xc, 0, sizeof(xc)); }
	void add(int n, int cx, int k) { n++; for(int i = n; i < c; i += lowBit(i)) { a[i] += k; xc[i] += k*cx; } }
	pii sum(int);
};
pii TreeArray::sum(int n) {
	int ta = 0, tx = 0; n++;
	for(int i = n; i > 0; i -= lowBit(i)) { ta += a[i]; tx += xc[i]; }
	return pii(ta, tx);
}

class Cow {
public:
	int loud, x, xo;
	void make() { scanf("%d %d", &loud, &x); }
};

bool cmp1(const Cow& c1, const Cow& c2) { return c1.x < c2.x; }
bool cmp2(const Cow& c1, const Cow& c2) { return c1.loud > c2.loud; }

int main()
{
	TreeArray ta;
	Cow c[N];
	int n;
	
	while(scanf("%d", &n) != EOF) {
		for(int i = 0; i < n; i++) c[i].make();
		ta.clear(n);
		sort(c, c+n, cmp1);
		for(int i = 0; i < n; i++) { c[i].xo = i; ta.add(i, c[i].x, 1); }
		sort(c, c+n, cmp2);
		int64 r = 0;
		for(int i = 0; i < n; i++) {
			ta.add(c[i].xo, c[i].x, -1);
			pii left = ta.sum(c[i].xo-1), right = ta.sum(n-1);
			right.first -= left.first; right.second -= left.second;
			r += (left.first*c[i].x-left.second+right.second-right.first*c[i].x)*c[i].loud;
		}
		printf("%lld\n", r);
	}
	
	return 0;
}