Problem: Example

Input

9
0 0 v
1 0 >
2 0


Output

9

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int main()
{
	int N;
	cin >> N;
	char c;
	vector<int> x(N), y(N), d(N);
	map<int, set<P>> mp1, mp2;
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> c;
		mp1[x[i]].insert(P(y[i], i));
		mp2[y[i]].insert(P(x[i], i));

		d[i] = c == '>' ? 0 : c == '^' ? 1 : c == '<' ? 2 : 3;
	}
	int res = 0;
	for (int i = 0; i < N; i++) {
		auto t1 = mp1;
		auto t2 = mp2;
		int p = i;
		int cnt = 0;
		while (1) {
			t1[x[p]].erase(P(y[p], p));
			t2[y[p]].erase(P(x[p], p));
			cnt++;
			if (d[p] == 3) {
				auto ite = t1[x[p]].lower_bound(P(y[p], 0));
				if (t1[x[p]].empty() || ite == t1[x[p]].end()) {
					break;
				}
				p = ite->second;
			}
			else if (d[p] == 0) {
				auto ite = t2[y[p]].lower_bound(P(x[p], 0));
				if (t2[y[p]].empty() || ite == t2[y[p]].end()) {
					break;
				}
				p = ite->second;
			}
			else if (d[p] == 1) {
				auto ite = t1[x[p]].upper_bound(P(y[p], 1e9));
				if (t1[x[p]].empty() || ite-- == t1[x[p]].begin()) {
					break;
				}
				p = ite->second;
			}
			else {
				auto ite = t2[y[p]].upper_bound(P(x[p], 1e9));
				if (t2[y[p]].empty() || ite-- == t2[y[p]].begin()) {
					break;
				}
				p = ite->second;
			}
		}
		res = max(res, cnt);
	}
	cout << res << endl;
	return 0;
}