Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define sz(x) ((int) (x).size())
- #define forn(i,n) for (int i = 0; i < int(n); ++i)
- #define forab(i,a,b) for (int i = int(a); i < int(b); ++i)
- #define all(x) (x).begin(), (x).end()
- typedef long long ll;
- typedef long double ld;
- const int INF = 1000001000;
- const ll INFL = 2000000000000001000;
- const int maxn = 3030;
- #define pb push_back
- int n;
- int x[maxn], y[maxn];
- char dir[maxn];
- int shr[maxn], k;
- vector<int> hor[maxn];
- vector<int> ver[maxn];
- int kx, ky;
- char buf[3];
- list<int> hl[maxn], vl[maxn];
- typedef list<int>::iterator IT;
- IT xit[maxn], yit[maxn];
- int mshr(int x[]) {
- forn(i, n) shr[i] = x[i];
- sort(shr, shr+n);
- k = unique(shr, shr+n) - shr;
- forn(i, n) x[i] = lower_bound(shr, shr+k, x[i]) - shr;
- return k;
- }
- void scan() {
- scanf("%d", &n);
- forn(i, n) {
- scanf("%d%d%s", &x[i], &y[i], buf);
- dir[i] = buf[0];
- }
- // cout << dir << endl;
- kx = mshr(x);
- ky = mshr(y);
- }
- void build() {
- forn(i, kx) {
- vl[i].clear();
- vl[i].push_back(-1);
- for (auto p: ver[i]) {
- vl[i].push_back(p);
- xit[p] = std::prev(vl[i].end());
- }
- vl[i].push_back(-1);
- }
- forn(i, ky) {
- hl[i].clear();
- hl[i].push_back(-1);
- for (auto p: hor[i]) {
- hl[i].push_back(p);
- yit[p] = std::prev(hl[i].end());
- }
- hl[i].push_back(-1);
- }
- }
- int go(int v) {
- int cnt = 0;
- while (true) {
- // cout << "v = " << v << endl;
- ++cnt;
- IT cx = xit[v], cy = yit[v];
- IT ocx = cx, ocy = cy;
- if (dir[v] == '>') { // ++x
- ++cy;
- } else if (dir[v] == '<') {
- --cy;
- } else if (dir[v] == 'v') {
- ++cx;
- } else if (dir[v] == '^') {
- --cx;
- // } else {
- // assert(!1);
- }
- int nv = v ^ *cx ^ *cy;
- if (nv == -1) {
- break;
- }
- vl[x[v]].erase(ocx);
- hl[y[v]].erase(ocy);
- v = nv;
- }
- return cnt;
- }
- void solve()
- {
- scan();
- forn(i, n) {
- ver[x[i]].pb(i);
- hor[y[i]].pb(i);
- }
- forn(i, kx) {
- sort(all(ver[i]), [](int i, int j) { return y[i] < y[j]; });
- }
- forn(i, ky) {
- sort(all(hor[i]), [](int i, int j) { return x[i] < x[j]; });
- }
- int res = 0;
- forn(i, n) {
- build();
- res = max(res, go(i));
- }
- cout << res << endl;
- }
- int main()
- {
- srand(2317);
- cout.precision(10);
- cout.setf(ios::fixed);
- #ifdef LOCAL
- assert(freopen("b.in", "r", stdin));
- #else
- #endif
- int tn = 1;
- for (int i = 0; i < tn; ++i)
- solve();
- #ifdef LOCAL
- cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << '\n';
- #endif
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement