If you move the smoke according to the wind, advancing time \(t\) costs a time complexity of \(O(t)\), for a total cost of \(O(N^2)\), which does not meet the execution time limit.
How can I avoid it?

Here, notice that all the smoke move in the same way according to the wind. This allows us to do the following:

Fix the smoke at the position that it appears, and move the fire and Takahashi according to the wind.

In other word, regarding that “the smoke moves according to the wind” and that “the fire and Takahashi moves in the opposite direction than the wind” is equivalent.

To achieve this, we need to follow these steps.

• First, generate smoke at cell \((0,0)\).

• Initialize the position of the fire at \((0,0)\) and Takahashi’s position at \((R,C)\).

• For each time \(t=1,2,\dots,N\), repeat the following.

  • Move the fire and Takahashi according to the following rule.
    • If \(S_i = \) N, move from \((r,c)\) to \((r+1,c)\).
    • If \(S_i = \) W, move from \((r,c)\) to \((r,c+1)\).
    • If \(S_i = \) S, move from \((r,c)\) to \((r-1,c)\).
    • If \(S_i = \) E, move from \((r,c)\) to \((r,c-1)\).
  • Generate smoke at the current position of the fire.
  • Print 1 if the current Takahashi’s position has smoke, and 0 otherwise.

The relative positions of the smoke, fire, and Takahashi are equivalent in the simulation above and the problem statement.
Since we have to move only two objects, the time complexity is reduced.

By managing the set of positions of the generated smoke in a data structure like set, the problem can be solved in a total of about \(O(N \log N)\) time.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;
using pi=pair<int,int>;

int main(){
  int n;
  pi t;
  string s;
  cin >> n >> t.first >> t.second;
  cin >> s;
  pi f={0,0};
  set<pi> st;
  st.insert(f);

  for(auto &nx : s){
    if(nx=='N'){
      t.first++;
      f.first++;
    }
    else if(nx=='W'){
      t.second++;
      f.second++;
    }
    else if(nx=='S'){
      t.first--;
      f.first--;
    }
    else{
      t.second--;
      f.second--;
    }
    
    st.insert(f);
    if(st.find(t)==st.end()){cout << "0";}
    else{cout << "1";}
  }cout << "\n";
  return 0;
}