# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
669102 | Do_you_copy | Bob (COCI14_bob) | C++17 | 130 ms | 25844 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.
/*
I find it wholesome to be alone the greater part of the time.
To be in company, even with the best, is soon wearisome and dissipating.
I love to be alone.
I never found the companion that was so companionable as solitude.
*/
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
mt19937_64 Rand(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e3 + 10;
//const int Mod = 1e9 + 7;
//const int inf =
int n, m;
int a[maxN][maxN];
int high[maxN][maxN];
int l[maxN][maxN];
int r[maxN][maxN];
void Init(){
cin >> n >> m;
for (int i = 1; i <= n; ++i){
for (int j = 1; j <= m; ++j){
cin >> a[i][j];
high[i][j] = (a[i][j] == a[i - 1][j]) ? high[i - 1][j] : 0;
++high[i][j];
}
}
ll ans = 0;
for (int i = 1; i <= n; ++i){
int j = 1;
while (j <= m){
int p = a[i][j];
int k = j;
while (j <= m && a[i][j] == p) ++j;
vector <int> S;
for (int x = k; x < j; ++x){
while (!S.empty() && high[i][S.back()] >= high[i][x]) S.pop_back();
l[i][x] = S.empty() ? k : S.back() + 1;
S.pb(x);
}
S.clear();
for (int x = j - 1; x >= k; --x){
while (!S.empty() && high[i][S.back()] > high[i][x]) S.pop_back();
r[i][x] = S.empty() ? j - 1 : S.back() - 1;
S.pb(x);
}
for (int x = k; x < j; ++x){
ans += 1LL * high[i][x] * (x - l[i][x] + 1) * (r[i][x] - x + 1);
}
}
}
cout << ans;
}
#define debug
#define taskname "test"
signed main(){
faster
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
int tt = 1;
//cin >> tt;
while (tt--){
Init();
}
if (fopen("timeout.txt", "r")){
ofstream timeout("timeout.txt");
timeout << signed(double(clock()) / CLOCKS_PER_SEC * 1000);
timeout.close();
#ifndef debug
cerr << "Time elapsed: " << signed(double(clock()) / CLOCKS_PER_SEC * 1000) << "ms\n";
#endif // debug
}
}
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... |