I need help (again)
Difference between en5 and en6, changed 1 character(s)
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>↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English pickle_juice2024 2024-03-14 04:26:05 1 Tiny change: 'roblem/C. \nFor som' -> 'roblem/C. \nFor som'
en5 English pickle_juice2024 2024-03-12 17:40:16 0 (published)
en4 English pickle_juice2024 2024-03-12 17:40:03 4 Tiny change: 'think so?)\nIf anyon' -> 'think so?).\nIf anyon'
en3 English pickle_juice2024 2024-03-12 17:39:50 4 Reverted to en1
en2 English pickle_juice2024 2024-03-12 17:39:02 4 Tiny change: 'think so?)\nIf anyon' -> 'think so?).\nIf anyon' (saved to drafts)
en1 English pickle_juice2024 2024-03-12 05:08:42 2635 Initial revision (published)