Submission #3727723

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
const double PI = 3.141592653589793238;
const double EPS = 1e-10;
typedef pair<ll, ll> P;
ll x[100000];
string d[100000];
int main() {
	int N;
	ll L;
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> d[i];
	}
	ll ans = 0;
	vector<P> v;
	{
		int i = 0;
		while (i < N) {
			vector<ll> tmp;
			tmp.push_back(x[i]);
			int j = i + 1;
			while (j < N) {
				if (d[i] != d[j]) break;
				tmp.push_back(x[j]);
				j++;
			}
			if (d[i] == "R") {
				ll r = x[j - 1];
				for (int k = j - 2; k >= i; k--) {
					ans += r - x[k] - 1;
					r--;
				}
				v.emplace_back(j - 1, tmp.size());
			}
			else {
				ll l = x[i];
				for (int k = i + 1; k < j; k++) {
					ans += x[k] - l - 1;
					l++;
				}
				v.emplace_back(i, tmp.size());
			}
			i = j;
		}
	}
	{
		int i = 0;
		if (d[v[i].first] == "L") {
			ans += (x[v[i].first] - 1)*(v[i].second);
			i++;
		}
		while (i + 1 < v.size()) {
			ans += (x[v[i + 1].first] - x[v[i].first] - 1)*max(v[i].second, v[i + 1].second);
			i += 2;
		}
		if (i < v.size()) {
			ans += (L - x[v[i].first])*(v[i].second);
		}
	}
	cout << ans << endl;
}

Submission Info

Judge Result