2106.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2106 on 2006-06-24 at 01:19:43 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 204800;

int v[N], vn, spo[N];

class Point {
public:
	int x, y, sc[2];
	void make(int i) { scanf("%d %d", &x, &y); v[i] = y; sc[0] = sc[1] = 0; }
	bool operator <(const Point&) const;
};
bool Point::operator <(const Point& p) const {
	if(x != p.x) return x < p.x;
	else return y < p.y;
}

class TreeArray {
public:
	int a[N];
public:
	void clear() { memset(a, 0, sizeof(a)); }
	int lowBit(int t) const { return t&(-t); }
	void add(int, int);
	int sum(int) const;
};
void TreeArray::add(int n, int m) {
	if(n == 0) { a[0] += m; return; }
	while(n < vn) {
		a[n] += m;
		n += lowBit(n);
	}
}
int TreeArray::sum(int n) const {
	if(n < 0) return 0;
	int r = a[0];
	while(n > 0) {
		r += a[n];
		n -= lowBit(n);
	}
	return r;
}

Point p[N];
TreeArray ta;

int disperse(int*, int);

int main()
{
	int n, i, j, k;

	while(scanf("%d", &n) != EOF && n != 0) {
		for(i = 0; i < n; i++) p[i].make(i);
		vn = disperse(v, n); sort(p, p+n);
		for(i = 0; i < n; i++) p[i].y = lower_bound(v, v+vn, p[i].y)-v;
		for(i = 0; i < 2; i++) {
			for(j = 0; j < n; j++) spo[j] = (i == 0) ? j : (n-1-j);
			ta.clear();
			for(j = 0; j < n; j++) {
				if(j == 0 || p[spo[j]].x != p[spo[j-1]].x)
					for(k = j-1; k >= 0 && p[spo[k]].x == p[spo[j-1]].x; k--)
						ta.add(p[spo[k]].y, 1);
				Point &cp = p[spo[j]];
				cp.sc[i] += ta.sum(cp.y-1); cp.sc[1-i] += ta.sum(vn-1)-ta.sum(cp.y);
			}
		}
		int ba = 0, bt = -1, bbv = -1; vector<int> bb;
		for(i = 0; i <= n; i++) {
			if(i == 0 || i == n || p[i].x != p[i-1].x) {
				if(bt >= ba) { 
					if(bt > ba) bb.clear();
					ba = bt; bb.push_back(bbv);
				}
				if(i != n) { bt = p[i].sc[0]; bbv = p[i].sc[1]; }
			} else if(bbv < p[i].sc[1]) { bt = p[i].sc[0]; bbv = p[i].sc[1]; }
			else bt = min(bt, p[i].sc[0]);
		}
		sort(bb.begin(), bb.end());
		printf("Stan: %d; Ollie:", ba);
		for(i = 0; i < bb.size(); i++) 
			if(i == 0 || bb[i] != bb[i-1]) printf(" %d", bb[i]);
		printf(";\n");
	}
	
	return 0;
}

int disperse(int* c, int n)
{
	int i, cn = 1; sort(c, c+n);
	for(i = 1; i < n; i++)
		if(c[i] != c[i-1]) c[cn++] = c[i];
	return cn;
}