Problem: Example

Input

9
0 0 v
1 0 >
2 0


Output

9

Solution (in CPP):

Solution:
/*  -*- coding: utf-8 -*-
 *
 * 2718.cc: Vector Field
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 3000;

/* typedef */

typedef pair<int,int> pii;
typedef vector<pii> vpii;
typedef map<int,int> mii;

/* global variables */

int xs[MAX_N], ys[MAX_N], cxs[MAX_N], cys[MAX_N], xis[MAX_N], yis[MAX_N];
char cs[MAX_N];
mii xmap, ymap;
bool used[MAX_N];
vpii xvs[MAX_N], yvs[MAX_N];

/* subroutines */

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int i = 0; i < n; i++) {
    scanf("%d %d %c", &xs[i], &ys[i], &cs[i]);
    cxs[i] = xs[i], cys[i] = ys[i];
    //printf("(%d,%d)[%c]\n", xs[i], ys[i], cs[i]);
  }

  sort(cxs, cxs + n);
  int xn = unique(cxs, cxs + n) - cxs;
  for (int i = 0; i < xn; i++) xmap[cxs[i]] = i;
  sort(cys, cys + n);
  int yn = unique(cys, cys + n) - cys;
  for (int i = 0; i < yn; i++) ymap[cys[i]] = i;

  for (int i = 0; i < n; i++) {
    xis[i] = xmap[xs[i]], yis[i] = ymap[ys[i]];
    xvs[yis[i]].push_back(pii(xis[i], i));
    yvs[xis[i]].push_back(pii(yis[i], i));
  }

  for (int i = 0; i < yn; i++) sort(xvs[i].begin(), xvs[i].end());
  for (int i = 0; i < xn; i++) sort(yvs[i].begin(), yvs[i].end());

  int maxd = 0;
  for (int st = 0; st < n; st++) {
    memset(used, false, sizeof(used));
    int d = 0;

    for (int i = st; i >= 0;) {
      used[i] = true, d++;
      int xi = xis[i], yi = yis[i];
      char c = cs[i];

      if (c == '>') {
	vpii &xv = xvs[yi];
	int k =
	  lower_bound(xv.begin(), xv.end(), pii(xi, i)) - xv.begin() + 1;
	while (k < xv.size() && used[xv[k].second]) k++;
	i = (k < xv.size()) ? xv[k].second : -1;
      }
      else if (c == '<') {
	vpii &xv = xvs[yi];
	int k =
	  lower_bound(xv.begin(), xv.end(), pii(xi, i)) - xv.begin() - 1;
	while (k >= 0 && used[xv[k].second]) k--;
	i = (k >= 0) ? xv[k].second : -1;
      }
      else if (c == 'v') {
	vpii &yv = yvs[xi];
	int k =
	  lower_bound(yv.begin(), yv.end(), pii(yi, i)) - yv.begin() + 1;
	while (k < yv.size() && used[yv[k].second]) k++;
	i = (k < yv.size()) ? yv[k].second : -1;
      }
      else {
	vpii &yv = yvs[xi];
	int k =
	  lower_bound(yv.begin(), yv.end(), pii(yi, i)) - yv.begin() - 1;
	while (k >= 0 && used[yv[k].second]) k--;
	i = (k >= 0) ? yv[k].second : -1;
      }
    }

    if (maxd < d) maxd = d;
    //printf("st=%d, d=%d\n", st, d);
  }

  printf("%d\n", maxd);
  return 0;
}