I am currently solving 1893C: https://mirror.codeforces.com/contest/1893/problem/C.
For some strange reason my code gives MLE when the space complexity of my code is O(n + m) (at least I think so?). If anyone could help me, it would be highly appreciated. My code:
Spoiler
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Data {
ll a, b;
};
const int MAX = 1e5 + 2;
const ll oo = 1e17;
vector<Data> a[MAX];
ll l[MAX], r[MAX], b[MAX], n, minn, maxx, total, res;
ll bs(ll l, ll r, ll y, ll x) {
int mid;
int res = 0;
while (l <= r) {
mid = (l + r) / 2;
if (a[y][mid].a >= x) {
res = mid;
r = mid - 1;
} else l = mid + 1;
}
return res;
}
void solve() {
cin >> n;
minn = 0; maxx = 0; total = 0;
for (int i = 1; i <= n; i++) {
b[i] = 0;
int m;
cin >> m >> l[i] >> r[i];
total += r[i] - l[i];
minn += l[i];
maxx += r[i];
if (minn > oo) minn = oo;
if (maxx > oo) maxx = oo;
Data temp = {
0,
0,
};
a[i].clear();
for (int j = 1; j <= m; j++) a[i].push_back(temp);
for (int j = 1; j <= m; j++) cin >> a[i][j - 1].a;
for (int j = 1; j <= m; j++) {
cin >> a[i][j - 1].b;
b[i] += a[i][j - 1].b;
}
}
map<ll, vector<ll>> m;
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < a[i].size(); j++) m[a[i][j].a].push_back(i);
}
for (auto i : m) {
if (i.first >= minn && i.first <= maxx) cnt++;
}
if (cnt < maxx - minn + 1) {
cout << 0 << "\n";
return;
}
res = LLONG_MAX;
for (int i = minn; i <= maxx; i++) {
ll total1 = total;
ll res1 = 0;
for (auto j : m[i]) {
total -= (r[j] - l[j]);
ll temp = a[j][bs(0, a[j].size() - 1, j, i)].b;
if (b[j] - temp <= l[j]) res1 += l[j] - (b[j] - temp);
else if (b[j] - temp <= r[j]) total += b[j] - temp - l[j];
else total += r[j] - l[j];
}
if (total < i - minn) res1 += i - minn - total;
res = min(res, res1);
total = total1;
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t;
cin >> t;
while (t--) solve();
}
Auto comment: topic has been updated by pickle_juice2024 (previous revision, new revision, compare).
Fixed the MLE, here's your TLE!
Submission: https://mirror.codeforces.com/contest/1893/submission/251179543
You iterate from minn to maxx but the maximum value of maxx-minn is very big.
l <= r <= 10^17
The reason for the MLE is that when iterating from minn to maxx and iterating through the elements of m[i] even if there was no element added to m[i] it will initialize to an empty vector. A simple check if m[i] exists fixes this.
Edit: I also fixed the TLE: https://mirror.codeforces.com/contest/1893/submission/251180328.
But I already have this:
This means that maxx — minn + 1 is at most cnt, which in turn is at most 2e5?
[ignore this i'm stupid]
I meant after that if, then maxx — minn + 1 <= cnt right?
Oh.. I'm stupid. Hmm now I need someone to help me understamd why this code TLE/MLEs..