AtCoder Beginner Contest 243 C - Collision 2

問題の要約
　xy座標平面上にN人の人がいる。人iは(Xi,Yi)にいる。
　L,Rからなる長さNの文字列Sがある。
　人iはSi=Rならば右向き(x軸の正の向き)に、Si=Lならば左向き(x軸の負の向き)に、一斉に同じ速度で歩きは始める。
　反対の向きに歩いている人同士が同じ地点に来ることを「衝突」と呼ぶ。
　すべての人が歩き続けたとき、衝突は発生するか?
制約
　2<=N<=2*10^5
　0<=Xi,Yi<=10^9
　i≠jならば(Xi,Yi)≠(Xj,Yj)
　SはLおよびRからなる長さNの文字列
入力
　N
　X1 Y1
　X2 Y2
　...
　XN YN
　S
考え方
　1,重要そうな文字列Sが最後に入力されるので、最初は単純にvectorなどを使ってデータを格納していく。
　2,人はx軸方向にしか歩かないので、y座標の値でx座標の値を取得できればよい。
　　データ構造としてmapを考える。
　3,右向きの人と左向きの人は分けて考えることができる。
　　mapを二つ用意する。
　4,右向きの人は一番左の人、左向きの人は一番右の人だけを考えればよい。
　　それぞれのmapについて、条件分岐によって更新していく。
　5,右向きの人に対しては左向きの人が格納されているmapを使って、左向きの人に対しては右向きの人が格納されているmapを使って検索する。
　　右向きの人と左向きの人が同じy座標にいて、右向きの人のx座標が左向きの人のx座標より少ないと衝突が発生することに注意する。
実際のプログラム
#include<iostream>
#include<vector>
#include<map>
#include<string>

using namespace std;

int main(){
  long long N;
  cin >> N;
  vector<pair<long long, long long>> XY(N);
  for(long long i = 0; i < N; i++){
    cin >> XY[i].first >> XY[i].second;
  }
  string S;
  cin >> S;
  
  map<long long,long long> mpLYX;
  map<long long,long long> mpRYX;
  for(long long i = 0; i < N; i++){
    long long X = XY[i].first;
    long long Y = XY[i].second;
    char C = S[i];
    if(C == 'L'){
      auto itr = mpLYX.find(Y);
      if(itr == mpLYX.end()){
        mpLYX[Y] = X;
      }else{
        if(itr->second < X){
          mpLYX[Y] = X;
        }
      }
    }else if(C == 'R'){
      auto itr = mpRYX.find(Y);
      if(itr == mpRYX.end()){
        mpRYX[Y] = X;
      }else{
        if(X < itr->second){
          mpRYX[Y] = X;
        }
      }
    }
  }
  
  bool flag = false;
  for(long long i = 0; i < N; i++){
    long long X = XY[i].first;
    long long Y = XY[i].second;
    char C = S[i];
    
    if(C == 'L'){
      auto itr = mpRYX.find(Y);
      if(itr != mpRYX.end()){
        if(itr->second < X){
          flag = true;
        }
      }
    }else if(C == 'R'){
      auto itr = mpLYX.find(Y);
      if(itr != mpLYX.end()){
        if(X < itr->second){
          flag = true;
        }
      }
    }
  }
  
  if(flag){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  
  return 0;
}