Submission #20456

#	Time	Username	Problem	Language	Result	Execution time	Memory
20456		kdh9949	Bob (COCI14_bob)	C++14	120 / 120	299 ms	30252 KiB

bob

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

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 / 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