답안 #20455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20455 2017-02-11T16:26:24 Z kdh9949 Bob (COCI14_bob) C++14
0 / 120
0 ms 1848 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);
			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++){
			while(!st[a[i][j]].empty()) st[a[i][j]].pop();
			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);
                         ^
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Runtime error 0 ms 1848 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -