Advertisement
Guest User

Untitled

a guest
Apr 21st, 2018
512
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.79 KB | None | 0 0
  1. #ifdef DEBUG
  2. #define _GLIBCXX_DEBUG
  3. #endif
  4.  
  5. #include <bits/stdc++.h>
  6.  
  7. using namespace std;
  8.  
  9. typedef long double ld;
  10.  
  11. #ifdef DEBUG
  12. #define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  13. #else
  14. #define eprintf(...) ;
  15. #endif
  16.  
  17. #define sz(x) ((int) (x).size())
  18. #define TASK "text"
  19.  
  20. const int inf = (int) 1.01e9;
  21. const long long infll = (long long) 1.01e18;
  22. const ld eps = 1e-9;
  23. const ld pi = acos((ld) -1);
  24.  
  25. mt19937 mrand(random_device{} ());
  26.  
  27. int rnd(int x) {
  28.   return mrand() % x;
  29. }
  30.  
  31. void precalc() {
  32. }
  33.  
  34. vector<string> c;
  35.  
  36. int read() {
  37.   int r, cc;
  38.   if (!(cin >> r) || !(cin >> cc)) {
  39.     return false;
  40.   }
  41.   while (cin.peek() != '\n') {
  42.     cin.get();
  43.   }
  44.   cin.get();
  45.   c.clear();
  46.   for (int i = 0; i < 2 * r - 1; i++) {
  47.     string row;
  48.     getline(cin, row);
  49.     c.push_back(row);
  50.   }
  51.   if (!(r & 1)) {
  52.     c.push_back("");
  53.     c.push_back(c[0]);
  54.     for (int i = 0; i < sz(c.back()); i++) {
  55.       if (c.back()[i] == '-') {
  56.         c.back()[i] = ' ';
  57.       }
  58.     }
  59.   }
  60.   return true;
  61. }
  62.  
  63. void getPoint(int i, int j, int &x, int &y) {
  64.   x = i / 2;
  65.   y = (j + 2) / 4 + x / 2;
  66. }
  67.  
  68. vector<vector<int>> es[3], d[4];
  69. vector<vector<int>> vals[2];
  70. vector<vector<int>> ps[2];
  71. vector<int> sums[2];
  72. long long res;
  73.  
  74. void solve1() {
  75.   int n = 0, m = 0;
  76.   for (int i = 0; i < sz(c); i++) {
  77.     const auto &row = c[i];
  78.     for (int j = 0; j < sz(row); j++) {
  79.       if (row[j] == 'x') {
  80.         int x, y;
  81.         getPoint(i, j, x, y);
  82.         n = max(n, x + 1);
  83.         m = max(m, y + 1);
  84.       }
  85.     }
  86.   }
  87.   for (int i = 0; i < 3; i++) {
  88.     es[i] = vector<vector<int>>(n, vector<int>(m));
  89.   }
  90.   for (int i = 0; i < sz(c); i++) {
  91.     const auto &row = c[i];
  92.     for (int j = 0; j < sz(row); j++) {
  93.       if (row[j] == '/') {
  94.         int x, y;
  95.         getPoint(i - 1, j + 1, x, y);
  96.         es[0][x][y] = true;
  97.       } else if (j + 1 < sz(row) && row[j] == 'x' && row[j + 1] == '-') {
  98.         int x, y;
  99.         getPoint(i, j, x, y);
  100.         es[1][x][y] = true;
  101.       } else if (row[j] == '\\') {
  102.         int x, y;
  103.         getPoint(i - 1, j - 1, x, y);
  104.         es[2][x][y] = true;
  105.       }
  106.     }
  107.   }
  108.   for (int i = 0; i < 3; i++) {
  109.     d[i] = es[i];
  110.   }
  111.   for (int i = n - 1; i >= 0; i--) {
  112.     for (int j = m - 1; j >= 0; j--) {
  113.       for (int dir = 0; dir < 3; dir++) {
  114.         if (!d[dir][i][j]) {
  115.           continue;
  116.         }
  117.         int ni = i, nj = j;
  118.         if (dir == 0 || dir == 2) {
  119.           ni++;
  120.         }
  121.         if (dir == 1 || dir == 2) {
  122.           nj++;
  123.         }
  124.         d[dir][i][j] += d[dir][ni][nj];
  125.       }
  126.     }
  127.   }
  128.   d[3] = vector<vector<int>>(n, vector<int>(m, 0));
  129.   for (int i = 0; i < n; i++) {
  130.     d[3][i][0] = 0;
  131.     for (int j = 1; j < m; j++) {
  132.       d[3][i][j] = (es[1][i][j - 1] ? d[3][i][j - 1] + 1 : 0);
  133.     }
  134.   }
  135.   vals[0] = vector<vector<int>>(m, vector<int>(n, 0));
  136.   sums[0] = vector<int>(m, 0);
  137.   ps[0] = vector<vector<int>>(m);
  138.   vals[1] = vector<vector<int>>(n + m - 1, vector<int>(n, 0));
  139.   sums[1] = vector<int>(n + m - 1, 0);
  140.   ps[1] = vector<vector<int>>(n + m - 1);
  141.   for (int i = n - 1; i >= 0; i--) {
  142.     for (int j = 0; j < m; j++) {
  143.       int xs[2] = {j, i - j + m - 1};
  144.       for (int it = 0; it < 2; it++) {
  145.         int x = xs[it];
  146.         auto &vals = ::vals[it][x];
  147.         auto &sum = sums[it][x];
  148.         auto &ps = ::ps[it][x];
  149.         while (sz(vals) > i + 1) {
  150.           sum -= vals.back();
  151.           vals.pop_back();
  152.         }
  153.         if (!d[2 * it][i][j]) {
  154.           for (int ii = 0; ii < sz(ps); ii++) {
  155.             if (ps[ii] < sz(vals)) {
  156.               vals[ps[ii]]--;
  157.             }
  158.           }
  159.           ps.clear();
  160.           sum = 0;
  161.         }
  162.       }
  163.       int t = (d[0][i][j] < d[2][i][j] ? 0 : 1);
  164.       res += sums[t][xs[t]];
  165.       for (int it = 0; it < 2; it++) {
  166.         int x = xs[it];
  167.         auto &vals = ::vals[it][x];
  168.         auto &sum = sums[it][x];
  169.         auto &ps = ::ps[it][x];
  170.         int curd = i - (!it ? d[1][i][j] : d[3][i][j]);
  171.         curd = max(0, curd);
  172.         vals[curd]++;
  173.         ps.push_back(curd);
  174.         sum++;
  175.       }
  176.     }
  177.   }
  178. }
  179.  
  180. void solve() {
  181.   res = 0;
  182.   for (int it = 0; it < 2; it++) {
  183.     solve1();
  184.     reverse(c.begin(), c.end());
  185.     for (int i = 0; i < sz(c); i++) {
  186.       for (int j = 0; j < sz(c[i]); j++) {
  187.         if (c[i][j] == '\\') {
  188.           c[i][j] = '/';
  189.         } else if (c[i][j] == '/') {
  190.           c[i][j] = '\\';
  191.         }
  192.       }
  193.     }
  194.   }
  195.   cout << res << "\n";
  196. }
  197.  
  198. int main() {
  199.   ios_base::sync_with_stdio(false);
  200.   precalc();
  201. #ifdef DEBUG
  202.   assert(freopen(TASK ".in", "r", stdin));
  203.   assert(freopen(TASK ".out", "w", stdout));
  204. #endif
  205.   while (read()) {
  206.     solve();
  207. #ifdef DEBUG
  208.     eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
  209. #endif
  210.   }
  211.   return 0;
  212. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement