oj.uz

답안 #20456

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20456 2017-02-11T16:31:45 Z kdh9949 Bob (COCI14_bob) C++14
120 / 120
 299 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 29604 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 29604 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 29604 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 29864 KB Output is correct

Subtask #5
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 29864 KB Output is correct

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 56 ms 29992 KB Output is correct

Subtask #7
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 293 ms 30252 KB Output is correct
2 Correct 133 ms 29604 KB Output is correct
3 Correct 146 ms 29604 KB Output is correct

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 299 ms 30252 KB Output is correct
2 Correct 166 ms 29604 KB Output is correct
3 Correct 133 ms 29604 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 269 ms 30252 KB Output is correct
2 Correct 153 ms 29604 KB Output is correct
3 Correct 156 ms 29604 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 253 ms 30252 KB Output is correct
2 Correct 149 ms 29604 KB Output is correct
3 Correct 149 ms 29604 KB Output is correct