Advertisement
Guest User

Untitled

a guest
Sep 27th, 2015
245
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.88 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define sz(x) ((int) (x).size())
  6. #define forn(i,n) for (int i = 0; i < int(n); ++i)
  7. #define forab(i,a,b) for (int i = int(a); i < int(b); ++i)
  8. #define all(x) (x).begin(), (x).end()
  9.  
  10. typedef long long ll;
  11. typedef long double ld;
  12.  
  13. const int INF = 1000001000;
  14. const ll INFL = 2000000000000001000;
  15.  
  16. const int maxn = 3030;
  17.  
  18. #define pb push_back
  19.  
  20. int n;
  21. int x[maxn], y[maxn];
  22. char dir[maxn];
  23. int shr[maxn], k;
  24. vector<int> hor[maxn];
  25. vector<int> ver[maxn];
  26. int kx, ky;
  27. char buf[3];
  28. list<int> hl[maxn], vl[maxn];
  29.  
  30. typedef list<int>::iterator IT;
  31.  
  32. IT xit[maxn], yit[maxn];
  33.  
  34. int mshr(int x[]) {
  35.     forn(i, n) shr[i] = x[i];
  36.     sort(shr, shr+n);
  37.     k = unique(shr, shr+n) - shr;
  38.     forn(i, n) x[i] = lower_bound(shr, shr+k, x[i]) - shr;
  39.     return k;
  40. }
  41.  
  42. void scan() {
  43.     scanf("%d", &n);
  44.     forn(i, n) {
  45.         scanf("%d%d%s", &x[i], &y[i], buf);
  46.         dir[i] = buf[0];
  47.     }
  48. //    cout << dir << endl;
  49.  
  50.     kx = mshr(x);
  51.     ky = mshr(y);
  52. }
  53.  
  54.  
  55. void build() {
  56.     forn(i, kx) {
  57.         vl[i].clear();
  58.         vl[i].push_back(-1);
  59.         for (auto p: ver[i]) {
  60.             vl[i].push_back(p);
  61.             xit[p] = std::prev(vl[i].end());
  62.         }
  63.         vl[i].push_back(-1);
  64.     }
  65.     forn(i, ky) {
  66.         hl[i].clear();
  67.         hl[i].push_back(-1);
  68.         for (auto p: hor[i]) {
  69.             hl[i].push_back(p);
  70.             yit[p] = std::prev(hl[i].end());
  71.         }
  72.         hl[i].push_back(-1);
  73.     }
  74. }
  75.  
  76. int go(int v) {
  77.     int cnt = 0;
  78.     while (true) {
  79. //        cout << "v = " << v << endl;
  80.         ++cnt;
  81.         IT cx = xit[v], cy = yit[v];
  82.         IT ocx = cx, ocy = cy;
  83.         if (dir[v] == '>') { // ++x
  84.             ++cy;
  85.         } else if (dir[v] == '<') {
  86.             --cy;
  87.         } else if (dir[v] == 'v') {
  88.             ++cx;
  89.         } else if (dir[v] == '^') {
  90.             --cx;
  91. //        } else {
  92. //            assert(!1);
  93.         }
  94.  
  95.         int nv = v ^ *cx ^ *cy;
  96.         if (nv == -1) {
  97.             break;
  98.         }
  99.         vl[x[v]].erase(ocx);
  100.         hl[y[v]].erase(ocy);
  101.         v = nv;
  102.     }
  103.     return cnt;
  104. }
  105.  
  106. void solve()
  107. {
  108.     scan();
  109.     forn(i, n) {
  110.         ver[x[i]].pb(i);
  111.         hor[y[i]].pb(i);
  112.     }
  113.     forn(i, kx) {
  114.         sort(all(ver[i]), [](int i, int j) { return y[i] < y[j]; });
  115.     }
  116.     forn(i, ky) {
  117.         sort(all(hor[i]), [](int i, int j) { return x[i] < x[j]; });
  118.     }
  119.  
  120.     int res = 0;
  121.     forn(i, n) {
  122.         build();
  123.         res = max(res, go(i));
  124.     }
  125.     cout << res << endl;
  126. }
  127.  
  128.  
  129. int main()
  130. {
  131.     srand(2317);
  132.     cout.precision(10);
  133.     cout.setf(ios::fixed);
  134.     #ifdef LOCAL
  135.     assert(freopen("b.in", "r", stdin));
  136.     #else
  137.     #endif
  138.     int tn = 1;
  139.     for (int i = 0; i < tn; ++i)
  140.         solve();
  141.     #ifdef LOCAL
  142.     cerr << "Time: " << double(clock()) / CLOCKS_PER_SEC << '\n';
  143.     #endif
  144. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement