Submission #974542

#	Time	Username	Problem	Language	Result	Execution time	Memory
974542		DAleksa	Two Dishes (JOI19_dishes)	C++17	74 / 100	4486 ms	297120 KiB

dishes

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct node {
    long long mx;
    long long add;
    long long set;
    bool both;
    node() {
        mx = 0;
        add = 0;
        set = 0;
        both = false;
    }
};

struct pt {
    int y;
    long long val;
};

const int N = 1e6 + 10;
const long long inf = 4e18;
int n, m;
long long a[N], p[N], b[N], q[N];
long long s[N], t[N];
int x[N], y[N];
vector<pt> all[N];
node st[4 * N];

void propagate(int index) {
    if(2 * index + 1 < 4 * N) {
        if(st[index].both) {
            long long val = st[index].set + st[index].add;
            st[2 * index].mx = val;
            st[2 * index].set = val;
            st[2 * index].add = 0;
            st[2 * index].both = true;
            st[2 * index + 1].mx = val;
            st[2 * index + 1].set = val;
            st[2 * index + 1].add = 0;
            st[2 * index + 1].both = true;
            st[index].add = 0;
            st[index].set = 0;
            st[index].both = false;
        } else {
            st[2 * index].mx += st[index].add;
            st[2 * index].add += st[index].add;
            st[2 * index + 1].mx += st[index].add;
            st[2 * index + 1].add += st[index].add;
            st[index].add = 0;
        }
    }
}

void update(int index, int l, int r, int L, int R, long long val) {
    if(l > r || r < L || R < l) return;
    if(L <= l && r <= R) {
        st[index].mx += val;
        st[index].add += val;
        return;
    }
    propagate(index);
    int mid = (l + r) / 2;
    update(2 * index, l, mid, L, R, val);
    update(2 * index + 1, mid + 1, r, L, R, val);
    st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx);
}

void modify(int index, int l, int r, int L, int R, long long val) {
    if(l > r || r < L || R < l) return;
    if(L <= l && r <= R) {
        st[index].mx = val;
        st[index].set = val;
        st[index].both = true;
        st[index].add = 0;
        return;
    }
    propagate(index);
    int mid = (l + r) / 2;
    modify(2 * index, l, mid, L, R, val);
    modify(2 * index + 1, mid + 1, r, L, R, val);
    st[index].mx = max(st[2 * index].mx, st[2 * index + 1].mx);
}

long long get(int index, int l, int r, int x) {
    if(l > r || r < x || x < l) return -inf;
    if(l == r) return st[index].mx;
    propagate(index);
    int mid = (l + r) / 2;
    return max(get(2 * index, l, mid, x), get(2 * index + 1, mid + 1, r, x));
}

int walk(int index, int l, int r, int x, long long val) {
    if(l > r || r < x) return r;
    if(l == r) {
        if(st[index].mx >= val) return l - 1;
        return l;
    }
    if(st[index].mx < val) return r;
    propagate(index);
    int mid = (l + r) / 2;
    int L = walk(2 * index, l, mid, x, val);
    if(L != mid) return L;
    return walk(2 * index + 1, mid + 1, r, x, val);
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i] >> s[i] >> p[i];
    for(int i = 1; i <= m; i++) cin >> b[i] >> t[i] >> q[i];
    a[0] = b[0] = 0;
    for(int i = 2; i <= n; i++) a[i] += a[i - 1];
    for(int i = 2; i <= m; i++) b[i] += b[i - 1];
    for(int i = 1; i <= n; i++) {
        if(a[i] > s[i]) {
            x[i] = -1;
            continue;
        }
        int l = 0, r = m;
        int ans = l;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[i] + b[mid] <= s[i]) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        x[i] = ans;
    }
    for(int i = 1; i <= m; i++) {
        if(b[i] > t[i]) {
            y[i] = -1;
            continue;
        }
        int l = 0, r = n;
        int ans = l;
        while(l <= r) {
            int mid = (l + r) / 2;
            if(a[mid] + b[i] <= t[i]) {
                ans = mid;
                l = mid + 1;
            } else r = mid - 1;
        }
        y[i] = ans;
    }
    long long add = 0;
    for(int i = 1; i <= n; i++) {
        if(x[i] == -1) continue;
        add += p[i];
        if(x[i] < m) all[x[i] + 1].push_back({i - 1, -p[i]});
    }
    for(int i = 1; i <= m; i++) {
        if(y[i] == -1) continue;
        all[i].push_back({y[i], q[i]});
    }
    for(int i = 1; i <= m; i++) {
        sort(all[i].begin(), all[i].end(), [&](pt p1, pt p2) {
            return p1.y > p2.y;
        });
    }
    // modify(1, 0, n, 1, n, 39);
    // for(int i = 0; i <= n; i++) cout << get(1, 0, n, i) << " ";
    // return 0;
    // cout << "POINTS:\n";
    // for(int i = 0; i <= m; i++) {
    //     for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n";
    // }
    for(int i = 0; i <= m; i++) {
        // cout << "#" << i << ":\nPOINTS:\n";
        for(pt p : all[i]) {
            int y = p.y;
            long long val = p.val;
            // cout << y << " " << val << "\n";
            update(1, 0, n, 0, y, val);
            long long mx = get(1, 0, n, y);
            int nxt = walk(1, 0, n, y + 1, mx);
            // cout << mx << " " << nxt << "\n";
            modify(1, 0, n, y, nxt, mx);
            // cout << "TREE:\n";
            // for(int j = 0; j <= n; j++) cout << get(1, 0, n, j) << " ";
            // cout << "\n";
        }
        // cout << "\n";
    }
    // for(int i = 1; i <= m; i++) {
    //     for(pt p : all[i]) cout << i << " " << p.y << " " << p.val << "\n";
    // }
    // for(int i = 1; i <= n; i++) cout << x[i] << " ";
    // cout << "\n";
    // for(int i = 1; i <= m; i++) cout << y[i] << " ";
    // cout << "\n";
    // cout << add << "\n";
    cout << get(1, 0, n, n) + add;
    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: 0 / 17
• Subtask 8: 0 / 9