I am currently solving 1893C: https://codeforces.net/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 summary="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();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
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 summary="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();↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
