oj.uz

Submission #165670

# Submission time Handle Problem Language Result Execution time Memory
165670 2019-11-28T07:40:49 Z Sensei Strah (COCI18_strah) C++17
110 / 110
 873 ms 39704 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e3;

char st[MAXN + 7][MAXN + 7];

int a[MAXN + 7];

long long table[MAXN + 7][MAXN + 7];

int N, M;

class SegmentTree {
private:
	pair<int, int> tree[4 * MAXN + 7];

	pair<int, int> merge (pair<int, int> x, pair<int, int> y) {
		if (x.first <= y.first) {
			return x;
		}

		return y;
	}

	void upd (int ss, int se, int si, int ui, int uv) {
		if (ss == se) {
			tree[si] = {uv, ui};
		}
		else {
			int mid = (ss + se) >> 1;

			if (ui <= mid) {
				upd(ss, mid, si * 2, ui, uv);
			}
			else {
				upd(mid + 1, se, si * 2 + 1, ui, uv);
			}

			tree[si] = merge(tree[si * 2], tree[si * 2 + 1]);
		}
	}

	pair<int, int> qry (int ss, int se, int si, int qs, int qe) {
		if (ss > qe || qs > se) {
			return {MAXN + 7, 0};
		}

		if (qs <= ss && se <= qe) {
			return tree[si];
		}

		int mid = (ss + se) >> 1;

		return merge(qry(ss, mid, si * 2, qs, qe), qry(mid + 1, se, si * 2 + 1, qs, qe));
	}

public:
	void update (int ui, int uv) {
		upd(1, M, 1, ui, uv);
	}

	int query (int qs, int qe) {
		return qry(1, M, 1, qs, qe).second;
	}
}
segtree;

long long calc (int i, int j) {
	return (i * 1LL * (i + 1)) * (j * 1LL * (j + 1)) / 4;
}

long long solve (int ss, int se) {
	if (ss > se) {
		return 0;
	}

	if (ss == se) {
		// cerr << ss << " " << ss << " " << se << " " << table[se - ss + 1][a[ss]] << "\n";
		// return table[se - ss + 1][a[ss]];

		// cerr << ss << " " << ss << " " << se << " " << calc(se - ss + 1, a[ss]) << "\n";
		return calc(se - ss + 1, a[ss]);
	}

	int mid = segtree.query(ss, se);

	long long ansl = solve(ss, mid - 1);
	long long ansr = solve(mid + 1, se);

	long long ans = ansl + ansr;

	// ans += table[se - ss + 1][a[mid]];

	ans += table[se - ss + 1][a[mid]];
	ans -= table[mid - 1 - ss + 1][a[mid]];
	ans -= table[se - (mid + 1) + 1][a[mid]];

	// cerr << ss << " " << mid << " " << se << " " << ans << "\n";

	return ans;
}

int main () {
	table[1][1] = 1;

	for (int i = 1; i <= MAXN; i++) {
		for (int j = 1; j <= MAXN; j++) {
			table[i][j] = table[i - 1][j] + calc(i, j);
		}
	}

	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		scanf("%s", st[i] + 1);
	}

	long long ans = 0;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (st[i][j] == '#') {
				a[j] = 0;
			}
			else {
				a[j]++;
			}

			segtree.update(j, a[j]);
		}

		ans += solve(1, M);
	}

	cout << ans << "\n";
	
	return 0;
}

Compilation message

strah.cpp: In function 'int main()':
strah.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", st[i] + 1);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31736 KB Output is correct
2 Correct 30 ms 31736 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31864 KB Output is correct
2 Correct 29 ms 31736 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 32412 KB Output is correct
2 Correct 41 ms 32376 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 32484 KB Output is correct
2 Correct 42 ms 32376 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 32308 KB Output is correct
2 Correct 43 ms 32420 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 212 ms 33628 KB Output is correct
2 Correct 457 ms 37240 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 462 ms 34424 KB Output is correct
2 Correct 782 ms 39288 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 33656 KB Output is correct
2 Correct 494 ms 37496 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 35324 KB Output is correct
2 Correct 550 ms 35584 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 873 ms 35876 KB Output is correct
2 Correct 787 ms 39704 KB Output is correct