oj.uz

답안 #165669

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
165669 2019-11-28T07:36:08 Z Sensei Strah (COCI18_strah) C++17
55 / 110
 67 ms 39544 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[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

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 31736 KB Output is correct
2 Correct 31 ms 31736 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 31736 KB Output is correct
2 Correct 30 ms 31736 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 32476 KB Output is correct
2 Correct 43 ms 32504 KB Output is correct

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 32480 KB Output is correct
2 Correct 43 ms 32508 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 32504 KB Output is correct
2 Correct 43 ms 32504 KB Output is correct

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 35 ms 34424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 40 ms 36860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 38 ms 35040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 35576 KB Output is correct
2 Incorrect 44 ms 38392 KB Output isn't correct

Subtask #10
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 48 ms 39544 KB Output isn't correct
2 Halted 0 ms 0 KB -