Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 2317 - Class Representative Witch

問題文 : 委員長の魔女

AOJ-ICPC の難易度設定には納得だけど実装つらかった(小並)

解法

偶奇で分けた累積和配列を使って, 各区間ごとに残った線分の長さを $O(\log n)$ 程度で求められれば OK.
$\[s_i,\ t_i\]$ 区間で爆破された点が偶数か奇数かで更に場合分けしていく.
ちなみに残った線分の長さは $10^14$ になることもあるので注意.

コード

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, m;
    static long long s[100000], t[100000], p[100001];
    static long long esum[100001], osum[100001];
    
    scanf("%d %d", &n, &m);
    
    for (int i = 0; i < n; i++) scanf("%lld %lld", s + i, t + i);
    for (int i = 0; i < m; i++) scanf("%lld", p + i);
    p[m++] = 0;
    sort(p, p + m);
    
    for (int i = 0; i < m; i++){
        if (i & 1){
            osum[i] = p[i] + (i ? osum[i - 1] : 0);
            osum[i + 1] = osum[i];
        }
        else {
            esum[i] = p[i] + (i ? esum[i - 1] : 0);
            esum[i + 1] = esum[i];
        }
    }
    
    
    long long ans = 0;
    
    for (int i = 0; i < n; i++){
        int mini = min(s[i], t[i]), maxi = max(s[i], t[i]);
        int minpos = upper_bound(p, p + m, mini) - p;
        int maxpos = upper_bound(p, p + m, maxi) - p - 1;
        
        if (minpos == m){
            ans += maxi - mini;
            continue;
        }
        
        long long tmp = osum[maxpos] - osum[minpos - 1] - esum[maxpos] + esum[minpos - 1];
        
        if ((maxpos - minpos + 1) & 1){
            if (s[i] > t[i]){
                //t[i] / ---- s[i]
                ans += s[i] + ((maxpos & 1) ? -tmp : tmp);
            }
            else {
                //s[i] --- / t[i]
                ans += ((maxpos & 1) ? tmp : -tmp) - s[i];
            }
        }
        else {
            ans += abs(t[i] - s[i]) + min(tmp, -tmp);
        }
    }
    
    printf("%lld\n", ans);
    
    return (0);
}