POJ 2352: Stars

Tatsuya Yatagawa
Programming Contest

問題

星がN個あって、それぞれにはX,Yという二次元座標が整数で与えられている。それぞれの星にはランクがつけられており、星のランクはその星より左下にある星の数で決まる(同じX座標あるいはY座標を持つものも含む)。このとき、ランク0からランクN-1までの星の個数を答えよ。

制約条件

1 <= N <= 15000
0 <= X, Y <= 32000

解法

早とちり常習犯の僕は、問題を読んだ瞬間に「二次元BIT」でいけると思い、コードを書いてSubmitしてMLE食らいました。

二次元BITだと空間計算量O(N^2)になってしまうのでそりゃそうです。

で、冷静に考えてみると、自分より下にあるかどうかは処理順でコントロールして、X方向の合計だけを1次元BITで管理することを考えます。

もう少し具体的に言うと星をY座標が小さい順(同じY座標だったらX座標が小さい順)に処理していきます。

常にBITには自分より下にある星しかないので、X方向で自分以下の座標を持つ星の数を合計すればランクが求まるというわけです。

この問題の計算量はざっくりO(NlogN)なのですが、問題で与えられている座標が高々32000なので、そのままの座標を使えばいいです。

以下のコードでは無駄に次元圧縮をして、大きめの問題にも対応できるようにしてあります。

// POJ 2352: Stars
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <algorithm>
#include <functional>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <vector>
#include <queue>
#include <bitset>
#include <string>
using namespace std;

#define REP(i,n) for(int i=0; i<n; i++)
#define REPP(i,s,e) for(int i=s; i<=e; i++)
#define PB(a) push_back(a)
#define MP(f,s) make_pair(f,s)
#define SZ(a) (int)(a).size()
#define ALL(a) (a).begin(), (a).end()
#define PRT(a) cerr << #a << " = " << (a) << endl
#define PRT2(a,b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << endl
#define PRT3(a,b,c) cerr << (a) << ", " << (b) << ", " << (c) << endl

typedef long long lint;
typedef pair<int,int> P;

int n;
int xs[15011];
int ys[15011];
int ans[15011];

struct BIT {
    int sz;
    vector<int> nodes;
    BIT(int n) :sz(n), nodes(n+1, 0) {}
    void add(int x, int val) {
        for(; x<=sz; x+=(x&-x)) nodes[x] += val;
    }
    int sum(int x) {
        int ret = 0;
        for(; x>0; x-=(x&-x)) ret += nodes[x];
        return ret;
    }
};

void solve() {
    vector<int> xv(n);
    vector<int> yv(n);
    REP(i,n) {
        xv[i] = xs[i];
        yv[i] = ys[i];
    }
    sort(ALL(xv));
    sort(ALL(yv));
    xv.erase(unique(ALL(xv)), xv.end());
    yv.erase(unique(ALL(yv)), yv.end());

    vector<P> pp;
    REP(i,n) {
        int xx = lower_bound(ALL(xv), xs[i]) - xv.begin() + 1;
        int yy = lower_bound(ALL(yv), ys[i]) - yv.begin() + 1;
        pp.push_back(P(yy, xx));
    }
    sort(ALL(pp));

    int X = SZ(xv);
    int Y = SZ(yv);
    BIT bit(X);

    memset(ans, 0, sizeof(ans));
    REP(i,n) {
        int xx = pp[i].second;
        int yy = pp[i].first;
        int s = bit.sum(xx);
        ans[s]++;
        bit.add(xx, 1);
    }

    REP(i,n) {
        printf("%d\n", ans[i]);
    }
}

void coding() {
    while(scanf("%d", &n) != EOF) {
        REP(i,n) scanf("%d %d", xs+i, ys+i);
        solve();
    }
}

// #define _LOCAL_TEST

int main() {
#ifdef _LOCAL_TEST
    clock_t startTime = clock();
    freopen("a.in", "r", stdin);
    // freopen("a.out", "w", stdout);
#endif

    coding();

#ifdef _LOCAL_TEST
    clock_t elapsedTime = clock() - startTime;
    cout << endl;
    cerr << (elapsedTime / 1000.0) << " sec elapsed." << endl;
    cerr << "This is local test" << endl;
    cerr << "Do not forget to comment out _LOCAL_TEST" << endl << endl;
#endif
}