Submission #10711

#	Time	Username	Problem	Language	Result	Execution time	Memory
10711		tncks0121	Bob (COCI14_bob)	C++14	120 / 120	228 ms	1692 KiB

bob

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