まず、

• 各 \(i = 1, 2, \ldots, H\) について「 \(i\) 行目にあるすべての壁の位置を列の昇順に並べた配列 \(A_i\) 」
• 各 \(j = 1, 2, \ldots, W\) について「 \(j\) 列目にあるすべての壁の位置を行の昇順に並べた配列 \(B_j\) 」

を作ります。

ただし、\(H, W\) は非常に大きくなりうるため、すべての行 \(i\) と列 \(j\) について配列 \(A_i\) と配列 \(B_j\) を陽に作ると計算量が大きくなってしまいます。 そこで、連想配列を用いるなどの方法によって、壁を \(1\) 個以上含む行 \(i\) や列 \(j\) についてのみ、配列 \(A_i\) や配列 \(B_j\) を陽に構築します。

各指示では、高橋君は \(l_i\) マス進み終わるか、壁・グリッドの端にぶつかるまで移動を続けます。 よって、指示を実行した後の最終的な高橋君の位置を求めるには、 \(d_i\) の方向にある最も近い壁・グリッドの端の位置が分かれば良いです。 これは、適切な \(A_i\) や \(B_j\) 上で二分探索をすることで \(\mathrm{O}(\log N)\) 時間で求めることができます。

例えば、高橋君の現在位置がマス \((R, C)\) のときに左向きに移動する指示を実行することを考えます。 このときの進行方向にある最も近い壁の位置（列番号）は \(A_R\)上で \(C\) 以下の最大の要素です。ただし、\(C\) 以下の要素が存在しないときは、進行方向においてグリッドの端までの間に壁はないとわかります。 \(A_R\) は事前に昇順にソートしてあるので、\(C\) 以下の最大の要素（あるいはそれが存在しないこと）は二分探索で求めることができます。

以上より、各指示を \(\mathrm{O}(\log N)\) 時間で実行できるので、指示全体で \(\mathrm{O}(Q \log N)\) 時間で実行できます。 \(A_i\) や \(B_j\) を作る時間（各要素を行・列の昇順にソートする時間など）を加味しても、本問題を \(\mathrm{O}((N+Q)\log N)\) 時間で解くことができます。

以下に、C++ 言語による本問題の正解例を記載します。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int h, w, n, r, c, Q;
map<int, vector<int>> amp, bmp;

int main(void)
{
  cin >> h >> w >> r >> c >> n;
  for(int i = 1; i <= n; i++){
    int rr, cc;
    cin >> rr >> cc;
    amp[rr].push_back(cc), bmp[cc].push_back(rr);
  }
  for(auto &p : amp) sort(p.second.begin(), p.second.end());
  for(auto &p : bmp) sort(p.second.begin(), p.second.end());
  
  cin >> Q;
  char d; int l;
  for(int i = 1; i <= Q; i++){
    cin >> d >> l;
    if(d == 'L'){
      auto it = amp.find(r); int lb = 0;
      if(it != amp.end()){
        vector<int> &vec = it->second;
        auto it2 = lower_bound(vec.begin(), vec.end(), c);
        if(it2 != vec.begin()) it2--, lb = *it2;
      }
      c = max(c-l, lb+1);
    }
    if(d == 'U'){
      auto it = bmp.find(c); int lb = 0;
      if(it != bmp.end()){
        vector<int> &vec = it->second;
        auto it2 = lower_bound(vec.begin(), vec.end(), r);
        if(it2 != vec.begin()) it2--, lb = *it2;
      }
      r = max(r-l, lb+1);
    }
    if(d == 'R'){
      auto it = amp.find(r); int ub = w+1;
      if(it != amp.end()){
        vector<int> &vec = it->second;
        auto it2 = upper_bound(vec.begin(), vec.end(), c);
        if(it2 != vec.end()) ub = *it2;
      }
      c = min(c+l, ub-1);
    }
    if(d == 'D'){
      auto it = bmp.find(c); int ub = h+1;
      if(it != bmp.end()){
        vector<int> &vec = it->second;
        auto it2 = upper_bound(vec.begin(), vec.end(), r);
        if(it2 != vec.end()) ub = *it2;
      }
      r = min(r+l, ub-1);
    }
    cout << r << " " << c << "\n";
  }
  
  return 0;
}