SHARE
TWEET

Untitled

a guest Mar 26th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 3005;
  6.  
  7. typedef vector<int> vi;
  8. //
  9. //struct wavelet_tree;;
  10. //
  11. //int pos = 0;
  12. //wavelet_tree nodes[4 * MAXN];
  13.  
  14. struct wavelet_tree {
  15.     int lo, hi;
  16.     wavelet_tree *l, *r;
  17.     vi b;
  18.  
  19.     wavelet_tree(int* from, int* to, int x, int y) {
  20.         lo = x, hi = y;
  21.         if (lo == hi || from >= to) return;
  22.         int mid = (lo + hi) / 2;
  23.         auto f = [mid](int x) { return x <= mid; };
  24.         b.reserve(to - from + 1);
  25.         b.push_back(0);
  26.         for (auto it = from; it != to; it++) {
  27.             b.push_back(b.back() + f(*it));
  28.         }
  29.         auto pivot = stable_partition(from, to, f);
  30.         l = new wavelet_tree(from, pivot, lo, mid);
  31.         r = new wavelet_tree(pivot, to, mid + 1, hi);
  32.     }
  33.  
  34.     int get(int l, int r, int x) {
  35.         if (l > r) {
  36.             return 0;
  37.         }
  38.         if (lo == hi) {
  39.             return r - l + 1;
  40.         }
  41.         int lb = b[l - 1], rb = b[r];
  42.         int toleft = rb - lb;
  43.         int toright = (r - l + 1) - toleft;
  44.         int mid = (lo + hi) / 2;
  45.         return x <= mid ? toright + this->l->get(lb + 1, rb, x) : this->r->get(l - lb, r - rb, x);
  46.     }
  47. };
  48.  
  49. int r, c;
  50. string f[2 * MAXN];
  51.  
  52. void rev() {
  53.     for (int i = 0; i < r; i++) {
  54.         for (int j = 0; j < 2 * c - 1; j++) {
  55.             std::swap(f[i][j], f[2 * r - 2 - i][j]);
  56.         }
  57.     }
  58.     for (int i = 0; i < 2 * r - 1; i++) {
  59.         for (int j = 0; j < 2 * c - 1; j++) {
  60.             if (f[i][j] == '/') {
  61.                 f[i][j] = '\\';
  62.             } else if (f[i][j] == '\\') {
  63.                 f[i][j] = '/';
  64.             }
  65.         }
  66.     }
  67.  
  68. //    for (int i = 0; i < 2 * r - 1; i++) {
  69. //        cerr << f[i] << '\n';
  70. //    }
  71. //    cerr << '\n';
  72. }
  73.  
  74. int16_t ur[2 * MAXN][2 * MAXN], rr[2 * MAXN][2 * MAXN], dr[2 * MAXN][2 * MAXN];
  75.  
  76. void precalc() {
  77.     for (int i = 0; i < 2 * r - 1; i++) {
  78.         memset(ur[i], 0, sizeof ur[i]);
  79.         memset(rr[i], 0, sizeof rr[i]);
  80.         memset(dr[i], 0, sizeof dr[i]);
  81.     }
  82.  
  83.     for (int i = 0; i < 2 * r - 1; i += 2) {
  84.         for (int j = 0; j < 2 * c - 1; j++) {
  85.             if (f[i][j] != 'x') {
  86.                 continue;
  87.             }
  88.             if (i - 2 >= 0 && j + 2 < 2 * c - 1 && f[i - 1][j + 1] == '/') {
  89.                 ur[i][j / 2] = ur[i - 2][j / 2 + 1] + (int16_t) 2;
  90.             }
  91.         }
  92.     }
  93.     for (int i = 0; i < 2 * r - 1; i += 2) {
  94.         for (int j = 2 * c - 2; j >= 0; j--) {
  95.             if (f[i][j] != 'x') {
  96.                 continue;
  97.             }
  98.             if (j + 4 < 2 * c - 1 && f[i][j + 1] == '-') {
  99.                 rr[i][j / 2] = rr[i][j / 2 + 2] + (int16_t) 4;
  100.             }
  101.         }
  102.     }
  103.     for (int i = 2 * r - 2; i >= 0; i -= 2) {
  104.         for (int j = 0; j < 2 * c - 1; j++) {
  105.             if (f[i][j] != 'x') {
  106.                 continue;
  107.             }
  108.             if (i + 2 < 2 * r - 1 && j + 2 < 2 * c - 1 && f[i + 1][j + 1] == '\\') {
  109.                 dr[i][j / 2] = dr[i + 2][j / 2 + 1] + (int16_t) 2;
  110.             }
  111.         }
  112.     }
  113. }
  114.  
  115. vector<pair<int, int> > diag[4 * MAXN];
  116. int arr[4 * MAXN];
  117.  
  118. int64_t solve() {
  119. //    cerr << "solve!\n";
  120.     precalc();
  121.  
  122.     for (auto &d : diag) {
  123.         d.clear();
  124.     }
  125.  
  126.     for (int i = 0; i < 2 * r - 1; i++) {
  127.         for (int j = 0; j < 2 * c - 1; j++) {
  128.             if (f[i][j] != 'x') {
  129.                 continue;
  130.             }
  131.             diag[i + j].emplace_back(i, j);
  132.         }
  133.     }
  134.  
  135.     int64_t ans = 0;
  136.     for (auto& d : diag) {
  137.         if (d.empty()) {
  138.             continue;
  139.         }
  140. //        cerr << "new diag!\n";
  141.  
  142.         memset(arr, 0, sizeof(int) * 2 * r);
  143.         for (int i = 0; i < (int) d.size(); i++) {
  144.             arr[d[i].first] = dr[d[i].first][d[i].second / 2] + d[i].first;
  145.         }
  146.         wavelet_tree * tree = new wavelet_tree(arr, arr + (2 * r - 1), 0, 4 * r + 4);
  147.  
  148.         for (int i = 0; i < (int) d.size(); i++) {
  149.             int _r = d[i].first, _c = d[i].second;
  150.             int l = std::min(ur[_r][_c / 2], (int16_t)(rr[_r][_c / 2] / 2));
  151.             int cur = tree->get(_r - l + 1, _r + 1, _r) - 1;
  152. //            cerr << _r << ' ' << _c << ' ' << ur[_r][_c] << ' ' << rr[_r][_c] << ' ' << cur << '\n';
  153.             ans += cur;
  154.         }
  155.     }
  156.     return ans;
  157. }
  158.  
  159. int main() {
  160.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  161.  
  162.     cin >> r >> c;
  163.     string str;
  164.     getline(cin, str);
  165.     for (int i = 0; i < 2 * r - 1; i++) {
  166.         getline(cin, str);
  167.         str.resize((size_t)(2 * c - 1));
  168.         f[i].swap(str);
  169.     }
  170.  
  171.     int64_t ans = solve();
  172.     rev();
  173.     ans += solve();
  174.  
  175.     cout << ans << '\n';
  176.  
  177.     return 0;
  178. }
  179.  
  180. /**
  181. 3 3
  182. x---x
  183.  \ /
  184.   x
  185.  / \
  186. x---x
  187.  
  188.  3 3
  189. x---x
  190.  \ /
  191.   x
  192.  / \
  193. x   x
  194.  
  195. 3 3
  196. x   x
  197.  \ /
  198.   x
  199.  / \
  200. x---x
  201.  
  202.  
  203. 2 3
  204.   x
  205.  / \
  206. x---x
  207.  
  208.  
  209. 4 10
  210. x   x---x---x   x
  211.      \ /   / \
  212.   x   x---x   x   x
  213.      / \ / \   \
  214. x   x---x---x---x
  215.    /   / \   \ / \
  216.   x---x---x---x---x
  217.  *
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top