Problem: Example

Input

9
0 0 v
1 0 >
2 0


Output

9

Solution (in CPP):

Solution:
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
using namespace std;
class BIT {
private:
	int size_; vector<int>x;
public:
	BIT() : size_(0), x(vector<int>()) {};
	BIT(int size__) : size_(size__) {
		x.resize(size__ + 1);
		for (int i = 0; i < size__ + 1; i++)x[i] = 0;
	}
	int size() { return size_; }
	void add(int r, int pp) {
		while (r <= size_) { x[r] += pp; r += r&-r; }
	}
	int sums(int r) {
		int cnt1 = 0; while (r >= 1) { cnt1 += x[r]; r -= r&-r; }
		return cnt1;
	}
	int sum(int l, int r) {
		return sums(r) - sums(l - 1);//Range [l, r]
	}
};
int n, x[5000], y[5000], dir[5000];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
vector<int>XX, YY, XXX, YYY, XR[3100], YR[3100];//XR=yoko, YR=tate
vector<tuple<int, int, int>>posit;
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		char c; cin >> x[i] >> y[i] >> c; swap(x[i], y[i]); XX.push_back(x[i]); YY.push_back(y[i]);
		if (c == 'v')dir[i] = 0; if (c == '>')dir[i] = 1; if (c == '^')dir[i] = 2; if (c == '<')dir[i] = 3;
	}
	sort(XX.begin(), XX.end()); sort(YY.begin(), YY.end()); XXX.push_back(XX[0]); YYY.push_back(YY[0]);
	for (int i = 1; i < XX.size(); i++) { if (XX[i - 1] != XX[i])XXX.push_back(XX[i]); }
	for (int i = 1; i < YY.size(); i++) { if (YY[i - 1] != YY[i])YYY.push_back(YY[i]); }
	for (int i = 0; i < n; i++) {
		int pos1 = lower_bound(XXX.begin(), XXX.end(), x[i]) - XXX.begin(); x[i] = pos1 + 1;
		int pos2 = lower_bound(YYY.begin(), YYY.end(), y[i]) - YYY.begin(); y[i] = pos2 + 1;
		XR[x[i]].push_back(y[i]); YR[y[i]].push_back(x[i]);
		posit.push_back(make_tuple(x[i], y[i], dir[i]));
	}
	vector<BIT> X(n + 2, BIT(n + 2)), Y(n + 2, BIT(n + 2)); sort(posit.begin(), posit.end());
	int maxn = 0;
	for (int i = 0; i < n; i++) {
		vector<tuple<int, int, int>>used;
		int cx = x[i], cy = y[i], cd = dir[i];
		for (int j = 0; j < n; j++) { X[x[j]].add(y[j], 1); Y[y[j]].add(x[j], 1); used.push_back(make_tuple(x[j], y[j], 0)); }
		bool flag = true; sort(used.begin(), used.end());
		int cnt2 = 0;
		while (true) {
			X[cx].add(cy, -1); Y[cy].add(cx, -1);
			int pos3 = lower_bound(used.begin(), used.end(), make_tuple(cx, cy, 0)) - used.begin();
			get<2>(used[pos3]) = 1;
			//--------------DOWN---------------
			if (cd == 0) {
				int L = cx, R = n + 2, M;
				while(true){
					M = (L + R) / 2;
					int E1 = Y[cy].sum(cx, M - 1);
					int E2 = Y[cy].sum(cx, M);
					if (E1 <= 0 && E2 >= 1) {
						cx = M;
						int pos4 = lower_bound(posit.begin(), posit.end(), make_tuple(cx, cy, 0)) - posit.begin(); cd = get<2>(posit[pos4]); break;
					}
					if (E1 >= 1)R = M;
					if (E2 <= 0)L = M;
					if (E2 <= 0 && M == n + 1) { flag = false; break; }
				}
			}
			//--------------UP---------------
			else if (cd == 2) {
				int L = 0, R = cx + 2, M;
				while (true) {
					M = (L + R) / 2;
					int E1 = Y[cy].sum(M - 1, cx);
					int E2 = Y[cy].sum(M, cx);
					if (E1 >= 1 && E2 <= 0) {
						cx = M - 1;
						int pos4 = lower_bound(posit.begin(), posit.end(), make_tuple(cx, cy, 0)) - posit.begin(); cd = get<2>(posit[pos4]); break;
					}
					if (E1 <= 0)R = M;
					if (E2 >= 1)L = M;
					if (E1 <= 0 && M == 0) { flag = false; break; }
				}
			}
			//--------------RIGHT---------------
			else if (cd == 1) {
				int L = cy, R = n + 2, M;
				while (true) {
					M = (L + R) / 2;
					int E1 = X[cx].sum(cy, M - 1);
					int E2 = X[cx].sum(cy, M);
					if (E1 <= 0 && E2 >= 1) {
						cy = M;
						int pos4 = lower_bound(posit.begin(), posit.end(), make_tuple(cx, cy, 0)) - posit.begin(); cd = get<2>(posit[pos4]); break;
					}
					if (E1 >= 1)R = M;
					if (E2 <= 0)L = M;
					if (E2 <= 0 && M == n + 1) { flag = false; break; }
				}
			}
			//--------------LEFT---------------
			else if (cd == 3) {
				int L = 0, R = cy + 2, M;
				while (true) {
					M = (L + R) / 2;
					int E1 = X[cx].sum(M - 1, cy);
					int E2 = X[cx].sum(M, cy);
					if (E1 >= 1 && E2 <= 0) {
						cy = M - 1;
						int pos4 = lower_bound(posit.begin(), posit.end(), make_tuple(cx, cy, 0)) - posit.begin(); cd = get<2>(posit[pos4]); break;
					}
					if (E1 <= 0)R = M;
					if (E2 >= 1)L = M;
					if (E1 <= 0 && M == 0) { flag = false; break; }
				}
			}
			cnt2++;
			if (flag == false) { break; }
		}
		for (int j = 0; j < n; j++) {
			int a1 = get<0>(used[j]), a2 = get<1>(used[j]), a3 = get<2>(used[j]);
			if (a3 == 1)continue;
			X[a1].add(a2, -1); Y[a2].add(a1, -1);
		}
		maxn = max(maxn, cnt2);
	}
	cout << maxn << endl;
	return 0;
}