oj.uz

Submission #10711

# Submission time Handle Problem Language Result Execution time Memory
10711 2014-11-09T14:51:18 Z tncks0121 Bob (COCI14_bob) C++14
120 / 120
 228 ms 1692 KB 
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int MAXL = 1050;
int N, M;
int A[2][MAXL], C[MAXL];
ll res;

int B[MAXL];


void solve (int l, int r) {
	int m = (l+r) >> 1;
	// 겹치는 부분에 대해서
	if(l > r) return;
	if(l == r) {
		res += C[m];
	}else {
		solve(l, m);
		solve(m+1, r);

		B[m] = C[m];
		for(int i = m-1; i >= l; i--) B[i] = min(B[i+1], C[i]);
		B[m+1] = C[m+1];
		for(int i = m+2; i <= r; i++) B[i] = min(B[i-1], C[i]);

		// 2 2 2 3 4 | 3 2 2 1 1
		ll sum = 0;
		for(int j = l, k = r; j <= m; j++) {
			while(k > m && B[j] >= B[k]) {
				sum += B[k];
				--k;
			}

			// B[m+1 .. k]  > B[j]
			res += (ll)B[j] * (k - m);
			// B[k+1 .. r] <= B[j]
			res += sum;
		}
	}
}

int main() {
	scanf("%d%d", &N, &M);
	for(int i = 0; i < N; i++) {
		int *now = A[i&1], *prv = A[~i&1];
		for(int j = 0; j < M; j++) {
			scanf("%d", &now[j]);
			if(now[j] != prv[j]) C[j] = 1; else ++C[j];
		}

		for(int j = 0; j < M; ) {
			int k = j;
			while(k < M && now[j] == now[k]) ++k;
			solve(j, k-1);
			j = k;
		}
	}

	printf("%lld\n", res);
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1692 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1692 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1692 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1692 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 1692 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 1692 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 1692 KB Output is correct
2 Correct 172 ms 1692 KB Output is correct
3 Correct 176 ms 1692 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 1692 KB Output is correct
2 Correct 168 ms 1692 KB Output is correct
3 Correct 176 ms 1692 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 204 ms 1692 KB Output is correct
2 Correct 176 ms 1692 KB Output is correct
3 Correct 176 ms 1692 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 1692 KB Output is correct
2 Correct 172 ms 1692 KB Output is correct
3 Correct 180 ms 1692 KB Output is correct