Submission #717579

#	Time	Username	Problem	Language	Result	Execution time	Memory
717579		walterw	Two Dishes (JOI19_dishes)	C++17	100 / 100	5026 ms	292764 KiB

dishes

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll

const int MAXN = 1e6 + 5;

int a[MAXN], s[MAXN], p[MAXN], b[MAXN], t[MAXN], q[MAXN];

int total = 0;

vector<pair<int, int>> events[MAXN];

struct node {
    int val;
    int lazymax = -1e16, lazyadd;
};

node tree[4 * 1000005];

void push(int x, int l, int r) {
    tree[x].val += tree[x].lazyadd;
    tree[x].val = max(tree[x].val, tree[x].lazymax);

    if (l != r) {
        tree[2 * x].lazymax = max(tree[2 * x].lazymax + tree[x].lazyadd, tree[x].lazymax);
        tree[2 * x].lazyadd += tree[x].lazyadd;

        tree[2 * x + 1].lazymax = max(tree[2 * x + 1].lazymax + tree[x].lazyadd, tree[x].lazymax);
        tree[2 * x + 1].lazyadd += tree[x].lazyadd;
    }

    tree[x].lazyadd = 0;
    tree[x].lazymax = -1e16;
}
void update(int x, int l, int r, int ql, int qr, int toadd, int tomax) {
    push(x, l, r);

    if (ql <= l && r <= qr) {
        tree[x].lazymax += toadd;
        tree[x].lazyadd += toadd;
        tree[x].lazymax = max(tree[x].lazymax, tomax);
        push(x, l, r);
        return;
    }

    if (l > qr || ql > r) return;

    int mid = (l + r) / 2;

    update(2 * x, l, mid, ql, qr, toadd, tomax);
    update(2 * x + 1, mid + 1, r, ql, qr, toadd, tomax);

    tree[x].val = max(tree[2 * x].val, tree[2 * x + 1].val);
}

int query(int x, int l, int r, int ql, int qr) {
    push(x, l, r);

    if (ql <= l && r <= qr) return tree[x].val;

    if (l > qr || ql > r) return -1e16;

    int mid = (l +r) / 2;

    return max(query(2 * x, l, mid, ql, qr), query(2 * x + 1, mid + 1, r, ql, qr));
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> s[i] >> p[i];
        a[i] += a[i - 1];
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i] >> t[i] >> q[i];
        b[i] += b[i - 1];
    }

    for (int i = 1; i <= n; i++) {
        int idx = upper_bound(b, b + m + 1, s[i] - a[i]) - b;

        if (idx == 0) continue;

        if (idx == m + 1) {
            total += p[i];
        } else {
            events[i].push_back({idx - 1, p[i]});
        }
    }

    for (int i = 1; i <= m; i++) {
        int idx = upper_bound(a, a + n + 1, t[i] - b[i]) - a;

        if (idx == 0) continue;
        if (idx == n + 1) {
            total += q[i];
        } else {
            total += q[i];
            events[idx].push_back({i - 1, -q[i]});
        }
    }

    for (int i = 1; i <= n; i++) {
        sort(events[i].begin(), events[i].end(), [&](pair<int, int> a, pair<int, int> b) {
           if (a.first == b.first) {
               return a.second < b.second;
           }
           return a.first > b.first;
        });

        for (auto [pos, val] : events[i]) {
            update(1, 0, m, 0, pos, val, -1e16);
            int largest = query(1, 0, m, 0, pos);

            update(1, 0, m, pos + 1, m, 0, largest);
        }
    }

    cout << total + query(1, 0, m, 0, m);
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9