(Analysis by Jonathan Paulson - jonathanpaulson@gmail.com)

Основна складність тут полягає в тому, що A і B настільки великі, що ми не можемо розглядати кожну нову корову окремо.

Ми повинні їх якось зібрати. Уявіть кожну корову як точку на числовій прямій (що відповідає її вазі). Кожна нова корова має (щонайбільше) одного сусіда ліворуч і одного сусіда праворуч, тому або нова корова має одного найближчого сусіда, або вона знаходиться точно між двома старими коровами. Таким чином, кожна стара корова «охоплює» певний діапазон на числовій прямій, де вона є найближчим сусідом, залежно від корови, яка стоїть ліворуч і праворуч (тобто наступна легша і наступна важча корова).

Підрахувавши, скільки нових корів покриває кожна стара плямиста корова, ми отримаємо відповідь. Кодувати це важко. Існує багато можливих помилок, що виникають окремо. У решті аналізу я розповім, як я це кодував.

По-перше: найпростіший спосіб розглядати корову та її сусідів одночасно — це сортувати їх, тож давайте це зробимо. Хороший спосіб уникнути крайніх випадків — додати додаткових старих корів на початку та в кінці, щоб кожна корова мала двох сусідів; якщо ми висадимо цих додаткових корів досить далеко, вони ні на що не вплинуть. Я вважав, що найпростіше розглядати кожну сусідню пару корів окремо.

Нехай S (S означає «початок») буде вагою корови зліва, а E (E означає «кінець») буде вагою корови праворуч. Ми хочемо обробляти інтервал [S + 1,E] (зауважте, що ми обробляємо праву кінцеву точку, але не ліву кінцеву точку; таким чином наші діапазони додають до всього інтервалу без жодної точки, яка враховується двічі або не враховується).

Нехай M=(S+E)/2 (M означає «середина»). Тоді ліва корова покриває інтервал [S+1,M], а права корова покриває інтервал [M+1,E] . Але не кожна точка є новою коровою: нам потрібно перетнути ці інтервали з [A,B] . Насправді ліва корова охоплює інтервал [max(S+1,A),min(M,B)], а права корова — інтервал [max(M+1,A),min(E,B)].

Отже, якщо ліва корова помічена, додайте лівий інтервал. Якщо помічена права корова, додайте правий інтервал. Вау! Насправді ми зробили одну помилку: ви це бачите? Ми не розглядали випадок, коли M було прямо посередині (якщо S і E парні або обидва непарні, M знаходиться прямо посередині; інакше M знаходиться в лівому інтервалі, де ми його розмістили). Якщо М прямо посередині, а ліва корова не помічена, а права корова помічена і М — нова корова, тоді ми не врахували М, а повинні були врахувати.

#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>

#define PB push_back
#define MP make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

int main() {
  ll n, A, B;
  scanf("%lld %lld %lld", &n, &A, &B);
  vector<pll> V;
  for(ll i=0; i<n; i++) {
    char buf[100];
    ll w;
    scanf("%s %lld", buf, &w);
    V.PB(MP(w, buf[0]=='S' ? 1 : 0));
  }
  ll INF = ll(1000)*1000*1000*1000;
  V.PB(MP(-INF, 0));
  V.PB(MP(INF, 0));
  sort(V.begin(), V.end());

  ll ans = 0;
  for(ll i=0; i+1<V.size(); i++) {
    ll S = V[i].X;
    ll E = V[i+1].X;
    ll M = (S+E)/2;

    if(V[i].Y==1) {
      ll s = max(A, S+1);
      ll e = min(B, M);
      if(e >= s) {
        ans += e-s+1;
      }
    }
    if(V[i+1].Y==1) {
      ll s = max(A, M+1);
      ll e = min(B, E);
      if(e >= s) {
        ans += e-s+1;
      }
    }
    if(V[i+1].Y==1 && V[i].Y==0 && (S%2)==(E%2) && A<=M && M<=B) {
      ans++; // Should count M
    }
  }
  printf("%lld\n", ans);
}