Submission #20457

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20457	2017-02-11T16:33:38 Z	kdh9949	Bob (COCI14_bob)	C++14	120 / 120	319 ms	30252 KB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, m, a[1010][1010], ld[1010][1010], ud[1010][1010], cnt, xx[1000010], s[1000010];
stack<int> *st[1000001];
ll ans;

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1, cnt = 0; i <= n; i++){
		for(int j = 1; j <= m; j++){
			scanf("%d", a[i] + j);
			xx[++cnt] = a[i][j];
		}
	}
	sort(xx + 1, xx + n * m + 1);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			a[i][j] = (int)(lower_bound(xx + 1, xx + n * m + 1, a[i][j]) - xx);
			if(!st[a[i][j]]) st[a[i][j]] = new stack<int>();
		}
		for(int j = 1; j <= m; j++){
			ld[i][j] = a[i][j - 1] == a[i][j] ? ld[i][j - 1] : j - 1;
			ud[i][j] = a[i - 1][j] == a[i][j] ? ud[i - 1][j] + 1 : 1;
			stack<int> &cst = *st[a[i][j]];
			int &cs = s[a[i][j]];
			while(!cst.empty() && cst.top() < ld[i][j]){
				cst.pop();
				cs = 0;
			}
			while(!cst.empty() && ud[i][cst.top()] >= ud[i][j]){
				int t = ud[i][cst.top()];
				cs -= cst.top() * t;
				cst.pop();
				if(!cst.empty()) cs += cst.top() * t;
				else cs += ld[i][j] * t;
			}
			if(!cst.empty()) cs += (j - cst.top()) * ud[i][j];
			else cs += (j - ld[i][j]) * ud[i][j];
			cst.push(j);
			ans += cs;
		}
		for(int j = 1; j <= m; j++){
			delete(st[a[i][j]]);
			st[a[i][j]] = 0;
			s[a[i][j]] = 0;
		}
	}
	printf("%lld\n", ans);
}

Compilation message

bob.cpp: In function 'int main()':
bob.cpp:10:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
bob.cpp:13:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", a[i] + j);
                         ^

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	53 ms	29604 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	29864 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	63 ms	29864 KB	Output is correct

Subtask #6
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	29992 KB	Output is correct

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	319 ms	30252 KB	Output is correct
2	Correct	146 ms	29604 KB	Output is correct
3	Correct	129 ms	29604 KB	Output is correct

Subtask #8
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	299 ms	30252 KB	Output is correct
2	Correct	143 ms	29604 KB	Output is correct
3	Correct	139 ms	29604 KB	Output is correct

Subtask #9
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	296 ms	30252 KB	Output is correct
2	Correct	146 ms	29604 KB	Output is correct
3	Correct	159 ms	29604 KB	Output is correct

Subtask #10
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	283 ms	30252 KB	Output is correct
2	Correct	146 ms	29604 KB	Output is correct
3	Correct	146 ms	29604 KB	Output is correct