AOJ 2317 - Class Representative Witch

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317

解法

をイベントとしてまとめて，左から2回見ていく．

1回目は，各糸上の爆発点の数を調べる． これは，(終了点までに見た爆発点) - (開始点までに見た爆発点) で得ることができる．

2回目は，残っている糸の長さを調べる． これは，今見ている点までで残っている糸と残っていない糸の数を管理することで数えることができる． ある糸の開始点が残っているのは，その点が使い魔が持っている側の点のときか，あるいは爆発点の数が偶数のとき． 同様に，ある糸の終了点が残っているのは，その点が使い魔が持っている側の点のときか，あるいは爆発点の数が偶数のとき． また，爆発点においては，残っている糸の数と残っていない糸の数が逆転する．

答えは int の範囲に収まらない場合もあることに注意． 

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 struct event
 7 {
 8   enum event_type { BEGIN, END, CUTOFF };
 9   event_type evt;
10   int pos;
11   int idx;
12   event(event_type e, int p, int i = -1) : evt(e), pos(p), idx(i) {}
13   bool operator<(const event& that) const { return pos < that.pos; }
14 };
15 
16 int main()
17 {
18   int N, M;
19   cin >> N >> M;
20   vector<pair<int,int> > intervals(N);
21   for (int i = 0; i < N; i++) {
22     cin >> intervals[i].first >> intervals[i].second;
23   }
24   vector<int> cutoffs(M);
25   for (int i = 0; i < M; i++) {
26     cin >> cutoffs[i];
27   }
28 
29   vector<event> v;
30   for (vector<pair<int,int> >::const_iterator it = intervals.begin(); it != intervals.end(); ++it) {
31     v.push_back(event(event::BEGIN, min(it->first, it->second), it - intervals.begin()));
32     v.push_back(event(event::END, max(it->first, it->second), it - intervals.begin()));
33   }
34   for (vector<int>::const_iterator it = cutoffs.begin(); it != cutoffs.end(); ++it) {
35     v.push_back(event(event::CUTOFF, *it));
36   }
37   sort(v.begin(), v.end());
38   vector<int> cnt(N, 0);
39   int acc = 0;
40   for (vector<event>::const_iterator it = v.begin(); it != v.end(); ++it) {
41     switch (it->evt) {
42       case event::BEGIN:
43         cnt[it->idx] = acc;
44         break;
45       case event::END:
46         cnt[it->idx] = acc - cnt[it->idx];
47         break;
48       case event::CUTOFF:
49         ++acc;
50         break;
51     }
52   }
53 
54   int on = 0, off = 0;
55   int prev = 0;
56   long long ans = 0LL;
57   for (vector<event>::const_iterator it = v.begin(); it != v.end(); ++it) {
58     ans += static_cast<long long>(it->pos - prev) * on;
59     switch (it->evt) {
60       case event::BEGIN:
61         if (intervals[it->idx].first == it->pos || cnt[it->idx] % 2 == 0) {
62           ++on;
63         } else {
64           ++off;
65         }
66         break;
67       case event::END:
68         if (intervals[it->idx].first == it->pos || cnt[it->idx] % 2 == 0) {
69           --on;
70         } else {
71           --off;
72         }
73         break;
74       case event::CUTOFF:
75         swap(on, off);
76         break;
77     }
78     prev = it->pos;
79   }
80   cout << ans << endl;
81   return 0;
82 }
aoj/2317.cc