27207 - JOIG Tour

작성일 | In

  • 문제 설명

    일자로 된 길 위 $N(4\leq N \leq100000)$개의 지점이 있습니다. $i$번째 지점의 위치는 $L_i(1 \leq L_i\leq10^{15})$, 그리고 그 지점 위 JOIG 중 하나의 글자가 써 있습니다. $Q(1\leq Q\leq10^5)$개의 쿼리가 주어집니다.

    $(s, e)$ : $s$에서 여행을 시작, JOIG를 순서대로 보고 $e$에서 여행을 마무리 할 때 최단거리 $D$를 구하시오.

  • 해설

    목표 글자가 $c$라면, 지금 현재 위치에서 왼쪽으로 가장 가까운 글자/오른쪽으로 가장 가까운 글자 2개만 고려하면 됩니다. 한 쿼리당 $2^4$번의 시뮬레이션을 사용해서 풀 수 있습니다. 현위치에서 가장 가까운 글자 위치는 이분탐색으로 찾을 수 있습니다.

  • 코드

    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
    int n;
vector<vector<ll>> g(4);
ll s, e;
ll cur = 0;
  
ll dfs(int id) {
    if(id == 4) {
        return abs(cur - e);
    }
    ll t = cur;
    int v = lower_bound(all(g[id]), cur) - g[id].begin();
    ll ret1 = LLINF, ret2 = LLINF;
    if(v != sz(g[id])) {
        ret1 = g[id][v] - cur;
        cur = g[id][v];
        ret1 += dfs(id + 1);
        cur = t;
    } 
    if(v > 0) {
        ret2 = cur - g[id][v-1];
        cur = g[id][v-1];
        ret2 += dfs(id + 1);
        cur = t;
    }
    return min(ret1, ret2);
}
  
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) {
        ll x; cin >> x;
        char c; cin >> c;
        for(int j=0; j<4; j++) if(c == "JOIG"[j]) {
            g[j].push_back(x);
        }
    }
    int q; cin >> q;
    while(q--) {
        cin >> s >> e;
        cur = s;
        cout << dfs(0) << '\n';
    }
}