# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
20456 | 2017-02-11T16:31:45 Z | kdh9949 | Bob (COCI14_bob) | C++14 | 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 29604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 29604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 59 ms | 29604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 46 ms | 29864 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 66 ms | 29864 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 29992 KB | Output is correct |
# | Verdict | Execution time | Memory | 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 |
# | Verdict | Execution time | Memory | 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 |
# | Verdict | Execution time | Memory | 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 |
# | Verdict | Execution time | Memory | 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 |