8 - Траектория обучения

#include <bits/stdc++.h>
using namespace std;
#define DB(v) cerr << #v << ' ' << v << endl
#define sz(v) i64(v.size())
#define For(i, a, b) for(i64 i = a;i <= b; ++i)

typedef long long i64;

const i64 N = 1e6 + 9;

template <typename T>
inline ostream &operator << (ostream &out, const vector <T> &v) {
    for(auto to: v)
        out << to << ' ';
    out << '\n';
    return out;
}

template <typename T>
inline ostream &operator << (ostream &out, const set <T> &v) {
    for(auto to: v)
        out << to << ' ';
    out << '\n';
    return out;
}


i64 n, m;

vector <i64> lesson_one, lesson_two, cost_one, cost_two;
i64 pos [N];

vector <i64> pref_sum;

inline i64 get_sum(i64 l, i64 r) {
    if(l > r)
        return 0;
    if(l == 0)
        return pref_sum[r];
    return pref_sum[r] - pref_sum[l - 1];
}

struct segment{
    i64 l, r;

    segment (i64 a = 0, i64 b = 0) {
        l = a;
        r = b;
    }

    bool operator < (const segment &other) const {
        return get_sum(l, r) < get_sum(other.l, other.r);
    }
};

struct answer {
    i64 l_one, r_one, l_two, r_two;
    i64 all_sum;
    answer (i64 a = 0, i64 b = 0, i64 c = 0, i64 d = 0, i64 e = 0) {
        tie(l_one, r_one, l_two, r_two, all_sum) = make_tuple(a, b, c, d, e);
    }

    bool operator < (const answer &other) const {
        return all_sum < other.all_sum;
    }

    void print() {
        cout << all_sum << '\n';
        cout << l_one << ' ' << r_one << '\n';
        cout << l_two << ' ' << r_two << '\n';
    }
};

int main()
{
#ifdef HOME
    freopen("input.txt","r",stdin);
#endif // HOME
    ios::sync_with_stdio(NULL); cin.tie(NULL);
    cin >> n >> m;
    memset(pos, -1, sizeof(pos));

    lesson_one.resize(n + 1);
    lesson_two.resize(m + 1);
    cost_one.resize(n + 1);
    cost_two.resize(m + 1);
    pref_sum.resize(m + 1);


    For(i, 1, n) {
        cin >> lesson_one[i];
    }
    For(i, 1, n) {
        cin >> cost_one[i];
    }
    For(i, 1, m) {
        cin >> lesson_two[i];
        pos[lesson_two[i]] = i;
    }
    For(i, 1, m) {
        cin >> cost_two[i];
        pref_sum[i] = pref_sum[i - 1] + cost_two[i];
    }

    answer result = answer(0, 0, 1, m, get_sum(1, m));

    set <i64> erased;
    set <segment> possible;

    for(i64 l = 1;l <= n; ++l) {
        possible.clear();
        erased.clear();
        erased.insert(0);
        erased.insert(m + 1);
        possible.insert(segment(1, m));

        i64 cur = 0;

        for(i64 r = l; r <= n; ++r) {
            cur += cost_one[r];
            i64 cur_pos = pos[lesson_one[r]];
            if(cur_pos != -1) {
                i64 l_pos = *(--erased.lower_bound(cur_pos)), r_pos = *erased.upper_bound(cur_pos);
                possible.erase(segment(l_pos + 1, r_pos - 1));
                if(l_pos + 1 <= cur_pos - 1)
                    possible.insert(segment(l_pos + 1, cur_pos - 1));
                if(cur_pos + 1 <= r_pos - 1)
                    possible.insert(segment(cur_pos + 1, r_pos - 1));
                erased.insert(cur_pos);
            }
            segment big = segment(0, 0);
            if(!possible.empty())
                big = (*(--possible.end()));
            if(get_sum(big.l, big.r) == 0)
                big = segment(0, 0);
            if(cur + get_sum(big.l, big.r) > result.all_sum) {
                result = answer(l, r, big.l, big.r, cur + get_sum(big.l, big.r));
            }
        }
    }

    result.print();
    return 0;
}