AOJ 2317 Class Representative Witch

問題

Class Representative Witch | Aizu Online Judge

解法

(S[i], T[i]) のペアごとに考えます。

S[i] と T[i] の間にいくつの P[j] があるかが分かれば(これは lower_bound を使えば高速にわかる), 2 つおきの累積和を使って目的の値が求められそうです。
というのが解法のイメージですが, これだけだと混乱しそうな(というか以前トライした時混乱してあきらめた)のでメモを書きました。

そういえば工夫のしどころですが, S[i] < T[i] のペアのみを考えることにし, S[i] > T[i] のペアは P, S, T をすべて -1 倍したものについて同じように考えることにすると実装が楽です。

const int MAXN = 100100;
int S[MAXN], T[MAXN];
int P[MAXN];
int N, M;
ll sumEven[MAXN], sumOdd[MAXN];

ll calc(int i) {
    int is = lower_bound(P, P+M, S[i]) - P;
    int it = lower_bound(P, P+M, T[i]) - P; it--;
    if (is == M || it == -1) return T[i] - S[i];
    ll ret = 0;
    if ((it-is)%2 == 0) {
        if (is%2) {
            ret = (sumOdd[it+2] - sumOdd[is]) - (sumEven[it+1] - sumEven[is+1]) - S[i];
        } else {
            ret = (sumEven[it+2] - sumEven[is]) - (sumOdd[it+1] - sumOdd[is+1]) - S[i];
        }
    } else {
        if (is%2) {
            ret = (sumOdd[it+1] - sumOdd[is]) - (sumEven[it+2] - sumEven[is+1]) + T[i] - S[i];
        } else {
            ret = (sumEven[it+1] - sumEven[is]) - (sumOdd[it+2] - sumOdd[is+1]) + T[i] - S[i];
        }
    }
    return ret;
}

ll solve() {
    memset(sumEven, 0, sizeof(sumEven));
    memset(sumOdd, 0, sizeof(sumOdd));
    for (int i = 0; i < M; i += 2) {
        sumEven[i+1] = sumEven[i];
        sumEven[i+2] = sumEven[i] + P[i];
    }
    for (int i = 1; i < M; i += 2) {
        sumOdd[i+2] = sumOdd[i] + P[i];
        sumOdd[i+1] = sumOdd[i+2];
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) if (S[i] < T[i]) {
        ll tmp = calc(i);
        ans += tmp;
    }
    return ans;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> S[i] >> T[i];
    for (int i = 0; i < M; i++) 
        cin >> P[i];
    sort(P, P+M);
    ll ans = solve();
    reverse(P, P+M);
    for (int i = 0; i < M; i++)
        P[i] *= -1;
    for (int i = 0; i < N; i++) {
        S[i] *= -1;
        T[i] *= -1;
    }
    ans += solve();
    cout << ans << endl;
    return 0;
}