Submission #165670

#	Time	Username	Problem	Language	Result	Execution time	Memory
165670		Sensei	Strah (COCI18_strah)	C++17	110 / 110	873 ms	39704 KiB

strah

#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 (stderr)

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 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11