Submission #3237683

---

Source Code Expand

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, L;
    cin >> N >> L;

    struct Usagi {
        ll x, follow_num;
        char d;
        bool move;
    };
    vector<Usagi> usa(N);
    for (ll i = 0; i < N; i++) {
        cin >> usa[i].x >> usa[i].d;
        usa[i].move = true;
    }
    

    //右向きウサギについて数える
    ll num = 0;
    for (ll i = 0; i < N; i++) {
        if (usa[i].d == 'R') {
            usa[i].follow_num = num++;
        } else {
            num = 0;
        }
    }

    //左向きウサギについて数える
    num = 0;
    for (ll i = N - 1; i >= 0; i--) {
        if (usa[i].d == 'L') {
            usa[i].follow_num = num++;
        } else {
            num = 0;
        }
    }

    //i番目のウサギが動くかどうかについて考える
    //前にいるウサギがこちらを向いており
    //向こうの方が後ろに続くウサギが多かったらこっちは動かない
    for (ll i = 0; i < N - 1; i++) {
        if (usa[i].d == 'R' && usa[i + 1].d == 'L') {
            if (usa[i].follow_num < usa[i + 1].follow_num) {
                usa[i].move = false;
            } else {
                usa[i + 1].move = false;
            }
            i++;
        }
    }

    ll ans = 0;

    //右向きウサギを限界まで動かす
    //行ける一番右のマス
    ll limit = L;
    for (ll i = N - 1; i >= 0; i--) {
        if (usa[i].d == 'L' || !usa[i].move) {
            limit = usa[i].x - 1;
        } else {
            ans += limit - usa[i].x;
            usa[i].x = limit;
            limit--;
        }
    }

    //左向きウサギを限界まで動かす
    limit = 1;
    for (ll i = 0; i < N; i++) {
        if (usa[i].d == 'R' || !usa[i].move) {
            limit = usa[i].x + 1;
        } else {
            ans += usa[i].x - limit;
            usa[i].x = limit;
            limit++;
        }
    }

    cout << ans << endl;
}

Submission Info

Judge Result