| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 713756 |
2023-03-23T02:28:43 Z |
ALTAKEXE |
Bob (COCI14_bob) |
C++14 |
|
181 ms |
17232 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair <int,int> ii;
const int N = 1e3 + 9;
const int oo = 1e10;
int n,m,a[N][N],high[N][N],l[N],r[N],res = 0;
void solve(int a[],int h[],bool kt)
{
stack <int> s;
h[0] = -oo;
s.push(0);
for (int i = 1;i <= m;i++)
{
while (h[i] < h[s.top()] && a[i] == a[s.top()]) s.pop();
l[i] = s.top() + 1;
s.push(i);
}
while (s.size()) s.pop();
s.push(m + 1);
h[m + 1] = -oo;
for (int i = m;i >= 1;i--)
{
while (h[i] <= h[s.top()] && a[i] == a[s.top()]) s.pop();
r[i] = s.top() - 1;
s.push(i);
}
int lim_r;
int tmp = res;
for (int i = 1;i <= m;i++)
{
if (kt) tmp = res;
tmp = res;
res += (i - l[i] + 1) * (r[i] - i + 1);
if (a[r[i] + 1] != a[i] || r[i] == m) lim_r = 1;
else lim_r = h[r[i] + 1] + 1;
// if (kt && i == m) cout<< res - tmp<<endl;
res += (h[i] - lim_r) * (i - l[i] + 1) * (r[i] - i + 1) + (lim_r - 1) * (i - l[i] + 1) * (r[i] - i + 1);
// if (kt) cout<<lim_r<<" ";
// if (kt) cout<<res - tmp<<endl;
}
// cout<<res - tmp<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
// freopen("test.inp","r",stdin);
// freopen("check1.out","w",stdout);
cin>>n>>m;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
cin>>a[i][j];
for (int i = 1;i <= n;i++)
for (int j = 1;j <= m;j++)
if (a[i][j] != a[i-1][j]) high[i][j] = 1;
else high[i][j] = high[i-1][j] + 1;
for (int i = 1;i <= n;i++)
solve(a[i],high[i],(i == 2));
cout<<res;
return 0;
}
Compilation message
bob.cpp: In function 'void solve(long long int*, long long int*, bool)':
bob.cpp:29:9: warning: variable 'tmp' set but not used [-Wunused-but-set-variable]
29 | int tmp = res;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
724 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
712 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
8748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
9164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
9292 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
9260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
17204 KB |
Output is correct |
| 2 |
Correct |
76 ms |
17116 KB |
Output is correct |
| 3 |
Correct |
71 ms |
17188 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
181 ms |
17224 KB |
Output is correct |
| 2 |
Correct |
77 ms |
17232 KB |
Output is correct |
| 3 |
Correct |
80 ms |
17216 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
17152 KB |
Output is correct |
| 2 |
Correct |
72 ms |
17148 KB |
Output is correct |
| 3 |
Correct |
69 ms |
17212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
142 ms |
17144 KB |
Output is correct |
| 2 |
Correct |
73 ms |
17228 KB |
Output is correct |
| 3 |
Correct |
87 ms |
17184 KB |
Output is correct |
