?? 2106.cpp
字號:
/* 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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -