I was solving the problem 364E - Пустые прямоугольники. The time complexity of my solution is $$$O(n^2k \log n)$$$, where $$$n \leq 2500$$$ and $$$k \leq 6$$$. The time limit for this problem is 12 seconds.
However, my submission 295732996 runs significantly slower on Codeforces compared to AtCoder and my local machine. (btw, I AC this problem using C++17 (GCC 7-32), 11155 ms, a little faster)
Comparisons
To investigate, I embedded a data generator that creates random matrices with uniformly distributed 0s and 1s, then ran the code on different platforms:
On Codeforces: 12437ms
On AtCoder: 4260ms
On My Local Machine (i3-6100, g++ 14.2.1, Arch Linux): 4596ms
The Code
Here is the implementation with the embedded data generator:
#include <algorithm>
#include <array>
#include <cstdint>
#include <iostream>
#include <random>
#include <string>
#include <vector>
using u8 = uint8_t;
using i64 = long long;
using i128 = __int128_t;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
template <typename T, int N>
struct StaticVector
{
int p;
std::array<T, N> v;
StaticVector() : p(0) {}
T &operator[](int x) { return v[x]; }
const T &operator[](int x) const { return v[x]; }
int size() const { return p; }
bool full() const { return p == (int)v.size(); }
void push_back(const T &t)
{
if (full()) return ;
v[p++] = t;
}
};
template <typename T, int K, typename Cmp>
StaticVector<T, K> merge(const StaticVector<T, K> &a, const StaticVector<T, K> &b, Cmp &&cmp)
{
StaticVector<T, K> c;
int i = 0, j = 0;
while (!c.full() && j < b.size()) {
if (cmp(a[i], b[j])) c.push_back(a[i++]);
else c.push_back(b[j++]);
}
while (!c.full()) c.push_back(a[i++]);
return c;
}
std::vector<std::vector<u8>> transpose(std::vector<std::vector<u8>> a)
{
int n = a.size();
int m = a[0].size();
std::vector<std::vector<u8>> b(m, std::vector<u8>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
b[j][i] = a[i][j];
}
}
return b;
}
template <int K>
i64 solve_details(std::vector<std::vector<u8>> a)
{
if (a.size() < a[0].size()) a = transpose(std::move(a));
if (a.size() == 1 && a[0].size() == 1) {
return a[0][0] == K;
} else {
int mid = a.size() / 2;
int n = a[0].size();
static std::vector<StaticVector<int, K + 2>> f;
static std::vector<StaticVector<int, K + 2>> g;
f.assign(n, {});
g.assign(n, {});
for (int i = mid - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) f[j].push_back(i);
}
}
for (int i = mid; i < (int)a.size(); i++) {
for (int j = 0; j < n; j++) {
if (a[i][j] == 1) g[j].push_back(i + 1);
}
}
i64 ans = 0;
for (int l = 0; l < n; l++) {
StaticVector<int, K + 2> fp, gp;
fp.push_back(mid);
gp.push_back(mid);
for (int t = 0; t <= K; t++) {
fp.push_back(-1);
gp.push_back(a.size() + 1);
}
for (int r = l + 1; r <= n; r++) {
fp = merge(std::move(fp), f[r - 1], std::greater<int>{});
gp = merge(std::move(gp), g[r - 1], std::less<int>{});
for (int i = 0; i <= K; i++) {
int uc = fp[i] - fp[i + 1];
int dc = gp[K - i + 1] - gp[K - i];
if (fp[i] == mid) uc--;
if (gp[K - i] == mid) dc--;
ans += uc * dc;
}
}
}
ans += solve_details<K>(std::vector(a.begin(), a.begin() + mid));
ans += solve_details<K>(std::vector(a.begin() + mid, a.end()));
return ans;
}
}
template <int K>
i64 solve(std::vector<std::vector<u8>> a, int k)
{
if (K < k) return solve<std::min(K + 1, 6)>(std::move(a), k);
return solve_details<K>(std::move(a));
}
int main()
{
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int n, m, k;
std::cin >> n >> m >> k;
std::vector a(n, std::vector<u8>(m));
std::mt19937 mt;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = mt() & 1;
}
}
std::cout << solve<0>(a, k) << std::endl;
}
Why does my code run so much slower on Codeforces? Is this due to differences in the hardware, compiler, or some other factor? Any insights would be appreciated.
