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); }