Algoogle

Algorithm for Programming Contest

AOJ 2317 Class Representative Witch

Category: AOJ Tag: implementation

Class Representative Witch

問題概要


解法


各糸について, 端点を切られる位置に移動させて考える.
そうするとある切断点について, 残る糸の始まりと終わりが現れることがあるので
その個数を数えておく.
終わりの点は, 残る糸の最後の点になるようにする.
使い魔が持っている点は糸を直近の切断点まで”伸ばす”.
伸ばした部分はあらかじめ答えから引いておく.
始点と終点の間に偶数個の切断点があれば使い魔が持っていない端点の糸も残る.
残る場合はその点を直近の切断点まで伸ばして, 伸ばした分を答えから引く.
そうでないなら一番近い切断点まで糸を切断する.

こうしてできた各端点について, 近い方をon, 遠い方をoffとしてカウントする.
あとはonになっている数とoffになってる数をもって切断点を順に舐めて, (上のonとoffとは違う)
各区間の長さをonの分答えを足す.
その点で終わる数の分onを減らして
onとoffを入れ替える.
そしてそこで始まる数の分onを増やす.

コード


(2317.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>

#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define INF 1e9

using namespace std;

typedef long long ll;

ll N, M;
ll p[100010], oncnt[100010], offcnt[100010];
ll s[100010], t[100010];

int main(){
    cin >> N >> M;
    M += 2;
    rep(i,N) cin >> s[i] >> t[i];
    rep(i,M-2) cin >> p[i];
    p[M-1] = INF;
    p[M-2] = 0;
    sort(p, p+M);
    ll ans = 0;
    rep(i,N){
        ll tmp = 0;
        if(s[i] > t[i]){
            ll *lb = lower_bound(p,p+M,s[i]), *lb2 = lower_bound(p,p+M,t[i]);
            lb--; lb2--;
            tmp = lb - lb2;
            ans -= *(lb+1) - s[i];
            offcnt[lb + 1 - p]--;
            if(tmp % 2){
                oncnt[lb2 + 1 - p]++;
            }
            else {
                ans -= t[i] - *lb2;
                oncnt[lb2 - p]++;
            }
        }
        else{
            ll *lb = lower_bound(p,p+M,t[i]), *lb2 = lower_bound(p,p+M,s[i]);
            lb--; lb2--;
            tmp = lb - lb2;
            ans -= s[i] - *lb2;
            oncnt[lb2 - p]++;
            if(tmp % 2){
                offcnt[lb - p]--;
            }
            else{
                ans -= *(lb+1) - t[i];
                offcnt[lb + 1 - p]--;
            }
        }
    }
    ll on = 0, off = 0;
    on += oncnt[0];
    repi(i,1,M){
        ans += on * (p[i] - p[i-1]);
        on += offcnt[i];
        swap(on, off);
        on += oncnt[i];
    }
    cout << ans << endl;
    return 0;
}

Comments