Google Code Jam 2013 Round1C The Great Wall

　本番はwordyなproblem statementに翻弄されてパニクった結果、smallしか解けませんでしたが、落ち着いて考えるとただの一次元の座標圧縮 + セグメント木でした。

　sampleにあるように端点はdiscreteだけど区間内に含まれる値はcontinuousというのがいやらしい感じですが、[a, b]を攻める => [a, b)を攻めると読み替えてもOKと気づくと素直に実装できます。本番中はこれに気づかず、0.5刻みの区間を整数の区間にマッピングして解くという無駄なことをしていました。

　あと、要素数が10^6くらいになるので、set/map（unordered_set/unordered_mapなら大丈夫だと思います。）ではなくvectorを使って処理しています。

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  

struct attack {
    int d;   // day
    int w;   // westmost
    int e;   // eastmost
    int s;   // strength

    attack(int d, int w, int e, int s) : d(d), w(w), e(e), s(s) {}
    
    bool operator<(const attack &x) const {
        return d < x.d;
    }
};

int seg[1<<22];

void init() {
    memset(seg, 0, sizeof(seg));
}

void update(int k, int l, int r, int a, int b, int x) {
    if (b <= l || r <= a)
        return;
    if (a <= l && r <= b)
        seg[k] = max(seg[k], x);
    else {
        int mid = (l + r) / 2;
        update(2*k+1, l, mid, a, b, x);
        update(2*k+2, mid, r, a, b, x);
        seg[k] = max(seg[k], min(seg[2*k+1], seg[2*k+2]));
    }
}

const int oo = 1<<30;
int query(int k, int l, int r, int a, int b) {
    if (b <= l || r <= a)
        return oo;
    if (a <= l && r <= b)
        return seg[k];
    else {
        int mid = (l + r) / 2;
        int x1 = query(2*k+1, l, mid, a, b);
        int x2 = query(2*k+2, mid, r, a, b);

        return max(seg[k], min(x1, x2));
    }
}

void solve() {
    int N;
    cin >> N;

    vector<int> pos;
    vector<attack> attacks;

    // read input data
    REP (i, N) {
        int di, ni, wi, ei, si, delta_di, delta_pi, delta_si;
        cin >> di >> ni >> wi >> ei >> si >> delta_di >> delta_pi >> delta_si;

        REP (j, ni) {
            attacks.push_back(attack(di, wi, ei, si));
            pos.push_back(wi);
            pos.push_back(ei);
            di += delta_di; wi += delta_pi; ei += delta_pi; si += delta_si;
        }
    }

    // axis compression
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    int L = pos.size();
    int M = attacks.size();
    REP (i, M) {
        attacks[i].w = lower_bound(pos.begin(), pos.end(), attacks[i].w) - pos.begin();
        attacks[i].e = lower_bound(pos.begin(), pos.end(), attacks[i].e) - pos.begin();
    }
    
    // simulate attacks
    sort(attacks.begin(), attacks.end());
    init();
    int cnt = 0;
    REP (i, M) {
        int j;

        // attack
        for(j = i; j < M && attacks[j].d == attacks[i].d; j++)
            if (query(0, 0, L, attacks[j].w, attacks[j].e) < attacks[j].s)
                ++cnt;

        // build the Wall
        for(j = i; j < M && attacks[j].d == attacks[i].d; j++)
            update(0, 0, L, attacks[j].w, attacks[j].e, attacks[j].s);

        i = --j;
    }

    cout << cnt << endl;
}

int main() {
    int T;
    cin >> T;

    REP (i, T) {
        printf("Case #%d: ", i+1);
        solve();
    }
    return 0;
}