Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MAXN = 3005;
- typedef vector<int> vi;
- //
- //struct wavelet_tree;;
- //
- //int pos = 0;
- //wavelet_tree nodes[4 * MAXN];
- struct wavelet_tree {
- int lo, hi;
- wavelet_tree *l, *r;
- vi b;
- wavelet_tree(int* from, int* to, int x, int y) {
- lo = x, hi = y;
- if (lo == hi || from >= to) return;
- int mid = (lo + hi) / 2;
- auto f = [mid](int x) { return x <= mid; };
- b.reserve(to - from + 1);
- b.push_back(0);
- for (auto it = from; it != to; it++) {
- b.push_back(b.back() + f(*it));
- }
- auto pivot = stable_partition(from, to, f);
- l = new wavelet_tree(from, pivot, lo, mid);
- r = new wavelet_tree(pivot, to, mid + 1, hi);
- }
- int get(int l, int r, int x) {
- if (l > r) {
- return 0;
- }
- if (lo == hi) {
- return r - l + 1;
- }
- int lb = b[l - 1], rb = b[r];
- int toleft = rb - lb;
- int toright = (r - l + 1) - toleft;
- int mid = (lo + hi) / 2;
- return x <= mid ? toright + this->l->get(lb + 1, rb, x) : this->r->get(l - lb, r - rb, x);
- }
- };
- int r, c;
- string f[2 * MAXN];
- void rev() {
- for (int i = 0; i < r; i++) {
- for (int j = 0; j < 2 * c - 1; j++) {
- std::swap(f[i][j], f[2 * r - 2 - i][j]);
- }
- }
- for (int i = 0; i < 2 * r - 1; i++) {
- for (int j = 0; j < 2 * c - 1; j++) {
- if (f[i][j] == '/') {
- f[i][j] = '\\';
- } else if (f[i][j] == '\\') {
- f[i][j] = '/';
- }
- }
- }
- // for (int i = 0; i < 2 * r - 1; i++) {
- // cerr << f[i] << '\n';
- // }
- // cerr << '\n';
- }
- int16_t ur[2 * MAXN][2 * MAXN], rr[2 * MAXN][2 * MAXN], dr[2 * MAXN][2 * MAXN];
- void precalc() {
- for (int i = 0; i < 2 * r - 1; i++) {
- memset(ur[i], 0, sizeof ur[i]);
- memset(rr[i], 0, sizeof rr[i]);
- memset(dr[i], 0, sizeof dr[i]);
- }
- for (int i = 0; i < 2 * r - 1; i += 2) {
- for (int j = 0; j < 2 * c - 1; j++) {
- if (f[i][j] != 'x') {
- continue;
- }
- if (i - 2 >= 0 && j + 2 < 2 * c - 1 && f[i - 1][j + 1] == '/') {
- ur[i][j / 2] = ur[i - 2][j / 2 + 1] + (int16_t) 2;
- }
- }
- }
- for (int i = 0; i < 2 * r - 1; i += 2) {
- for (int j = 2 * c - 2; j >= 0; j--) {
- if (f[i][j] != 'x') {
- continue;
- }
- if (j + 4 < 2 * c - 1 && f[i][j + 1] == '-') {
- rr[i][j / 2] = rr[i][j / 2 + 2] + (int16_t) 4;
- }
- }
- }
- for (int i = 2 * r - 2; i >= 0; i -= 2) {
- for (int j = 0; j < 2 * c - 1; j++) {
- if (f[i][j] != 'x') {
- continue;
- }
- if (i + 2 < 2 * r - 1 && j + 2 < 2 * c - 1 && f[i + 1][j + 1] == '\\') {
- dr[i][j / 2] = dr[i + 2][j / 2 + 1] + (int16_t) 2;
- }
- }
- }
- }
- vector<pair<int, int> > diag[4 * MAXN];
- int arr[4 * MAXN];
- int64_t solve() {
- // cerr << "solve!\n";
- precalc();
- for (auto &d : diag) {
- d.clear();
- }
- for (int i = 0; i < 2 * r - 1; i++) {
- for (int j = 0; j < 2 * c - 1; j++) {
- if (f[i][j] != 'x') {
- continue;
- }
- diag[i + j].emplace_back(i, j);
- }
- }
- int64_t ans = 0;
- for (auto& d : diag) {
- if (d.empty()) {
- continue;
- }
- // cerr << "new diag!\n";
- memset(arr, 0, sizeof(int) * 2 * r);
- for (int i = 0; i < (int) d.size(); i++) {
- arr[d[i].first] = dr[d[i].first][d[i].second / 2] + d[i].first;
- }
- wavelet_tree * tree = new wavelet_tree(arr, arr + (2 * r - 1), 0, 4 * r + 4);
- for (int i = 0; i < (int) d.size(); i++) {
- int _r = d[i].first, _c = d[i].second;
- int l = std::min(ur[_r][_c / 2], (int16_t)(rr[_r][_c / 2] / 2));
- int cur = tree->get(_r - l + 1, _r + 1, _r) - 1;
- // cerr << _r << ' ' << _c << ' ' << ur[_r][_c] << ' ' << rr[_r][_c] << ' ' << cur << '\n';
- ans += cur;
- }
- }
- return ans;
- }
- int main() {
- ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- cin >> r >> c;
- string str;
- getline(cin, str);
- for (int i = 0; i < 2 * r - 1; i++) {
- getline(cin, str);
- str.resize((size_t)(2 * c - 1));
- f[i].swap(str);
- }
- int64_t ans = solve();
- rev();
- ans += solve();
- cout << ans << '\n';
- return 0;
- }
- /**
- 3 3
- x---x
- \ /
- x
- / \
- x---x
- 3 3
- x---x
- \ /
- x
- / \
- x x
- 3 3
- x x
- \ /
- x
- / \
- x---x
- 2 3
- x
- / \
- x---x
- 4 10
- x x---x---x x
- \ / / \
- x x---x x x
- / \ / \ \
- x x---x---x---x
- / / \ \ / \
- x---x---x---x---x
- *
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement