Advertisement
Guest User

Untitled

a guest
Mar 26th, 2019
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.95 KB | None | 0 0
  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. *
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement