Submission #366910

#	Time	Username	Problem	Language	Result	Execution time	Memory
366910		valerikk	Two Dishes (JOI19_dishes)	C++17	100 / 100	4681 ms	144512 KiB

dishes

#include <bits/stdc++.h>

typedef long long ll;

#define set set1

using namespace std;

const int N = 1e6 + 7;
const ll INF = 1e18 + 100;

ll mx[4 * N];
ll delta[4 * N];

void apply(int v, ll val) {
    mx[v] += val;
    delta[v] += val;
}

void push(int v) {
    apply(2 * v, delta[v]);
    apply(2 * v + 1, delta[v]);
    delta[v] = 0;
}

void modify(int v, int tl, int tr, int l, int r, ll val) {
    if (tl >= r || tr <= l)
        return;
    if (tl >= l && tr <= r) {
        apply(v, val);
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    modify(2 * v, tl, tm, l, r, val);
    modify(2 * v + 1, tm, tr, l, r, val);
    mx[v] = max(mx[2 * v], mx[2 * v + 1]);
}

void set(int v, int l, int r, int pos, ll val) {
    if (r - l == 1) {
        mx[v] = max(mx[v], val);
    } else {
        push(v);
        int m = (l + r) / 2;
        if (pos < m)
            set(2 * v, l, m, pos, val);
        else 
            set(2 * v + 1, m, r, pos, val);
        mx[v] = max(mx[2 * v], mx[2 * v + 1]);
    }
}

ll query(int v, int tl, int tr, int l, int r) {
    if (tl >= r || tr <= l)
        return -INF;
    if (tl >= l && tr <= r)
        return mx[v];
    push(v);
    int tm = (tl + tr) / 2;
    return max(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm, tr, l, r));
}

int n, m;
ll a[N], b[N];
ll s[N], t[N];
ll p[N], q[N];

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    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];
    }
    ll sum = 0;
    vector<pair<pair<int, int>, ll>> events;
    for (int i = 1; i <= n; i++) {
        if (a[i] > s[i])
            continue;
        // cout << "Donburi " << i << endl;
        int ind = upper_bound(b, b + m + 1, s[i] - a[i]) - b - 1;
        if (ind == m)
            sum += p[i];
        else 
            events.push_back({{i, -ind}, p[i]});
    }
    for (int i = 1; i <= m; i++) {
        if (b[i] > t[i]) 
            continue;
        // cout << "Curry " << i << endl;
        int ind = upper_bound(a, a + n + 1, t[i] - b[i]) - a - 1;
        sum += q[i];
        if (ind != n)
            events.push_back({{ind + 1, -(i - 1)}, -q[i]});
    }
    sort(events.begin(), events.end());
    /* vector<pair<pair<int, int>, ll>> temp;
    for (auto &ev : events) {
        if (temp.empty() || ev.first != temp.back().first)
            temp.push_back(ev);
        else 
            temp.back().second += ev.second;
    }
    events = temp; */
    for (auto &ev : events) {
        int pos = -ev.first.second;
        ll val = ev.second;
        ll down = query(1, 0, m + 1, 0, pos + 1);
        modify(1, 0, m + 1, 0, pos + 1, val);
        if (pos != m)
            set(1, 0, m + 1, pos + 1, down);
        /* for (int i = 0; i <= m; i++) 
            cout << query(1, 0, m + 1, i, i + 1) << " ";
        cout << endl; */
    }
    cout << sum + mx[1] << endl;
    return 0;
}

• 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