Problem: Example

Input

9
0 0 v
1 0 >
2 0


Output

9

Solution (in CPP):

Solution:
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
using llong = long long;

struct node {
        int l, r, u, d;
        char dir;
};

using pi = pair<int, int>;
map<int, set<pi>> x_axis;
map<int, set<pi>> y_axis;
vector<node> nodes;
int n;
int X[3005], Y[3005];
char d;

void build() {
        for (int i = 1; i <= n; i++) {
                int x = X[i];
                int y = Y[i];
                nodes[i].r = (x_axis[y].upper_bound(pi(x, 100000)))->second;
                nodes[i].d = (y_axis[x].upper_bound(pi(y, 100000)))->second;

                {
                        auto itr = x_axis[y].lower_bound(pi(x, -1));
                        itr--;
                        nodes[i].l = itr->second;
                }
                {
                        auto itr = y_axis[x].lower_bound(pi(y, -1));
                        itr--;
                        nodes[i].u = itr->second;
                }
        }
}

int dfs(int u) {
        if (u == 0) return 0;

        nodes[nodes[u].u].d = nodes[u].d;
        nodes[nodes[u].d].u = nodes[u].u;
        nodes[nodes[u].l].r = nodes[u].r;
        nodes[nodes[u].r].l = nodes[u].l;

        switch(nodes[u].dir) {
                case '^' :
                        return dfs(nodes[u].u) + 1;
                        break;
                case 'v' :
                        return dfs(nodes[u].d) + 1;
                        break;
                        break;
                case '<' :
                        return dfs(nodes[u].l) + 1;
                        break;
                case '>' :
                        return dfs(nodes[u].r) + 1;
                        break;
        }
        return 0;
}

int main() {
        cin >> n;
        nodes.resize(n + 1);
        for (int i = 1; i <= n; i++) {
                cin >> X[i] >> Y[i] >> d;
                int x = X[i];
                int y = Y[i];
                nodes[i].dir = d;

                if (x_axis.count(y) == 0) {
                        x_axis[y].insert(pi(-1000000001, 0));
                        x_axis[y].insert(pi(1000000001, 0));
                }
                if (y_axis.count(x) == 0) {
                        y_axis[x].insert(pi(-1000000001, 0));
                        y_axis[x].insert(pi(1000000001, 0));
                }

                x_axis[y].insert(pi(x, i));
                y_axis[x].insert(pi(y, i));
        }

/*
        build();
        for (int i = 1; i <= n; i++) {
                printf("%d %d %d %d", nodes[i].l, nodes[i].r, nodes[i].u, nodes[i].d);
                cout << endl;
        }
        */

        int ans = 0;
        for (int i = 1; i <= n; i++) {
                build();
                ans = max(ans, dfs(i));
        }
        cout << ans << endl;
}