# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
20455 | kdh9949 | Bob (COCI14_bob) | C++14 | 0 ms | 1848 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |