Submission #1189960

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189960		onbert	Two Dishes (JOI19_dishes)	C++20	54 / 100	838 ms	98016 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
    int mn, mx;
    bool sorted;
};
struct thing {
    int asgn, del;
};

void pass(thing &a, thing b) {
    if (b.asgn != -1) a = b;
    else if (a.asgn != -1) a.asgn += b.del;
    else a.del += b.del;
}
node merge(node a, node b) {
    node cur;
    cur.mn = min(a.mn, b.mn);
    cur.mx = max(a.mx, b.mx);
    cur.sorted = (a.sorted && b.sorted && (a.mx <= b.mn));
    return cur;
}
const int maxn = 1e6 + 5, maxN = 4e6 + 5, INF = 1e16;
int n, m;
int a[maxn], S[maxn], P[maxn];
int b[maxn], T[maxn], Q[maxn];
vector<pair<int, int>> pre[maxn], suf[maxn];

node seg[maxN];
thing lazy[maxN];
void build(int id, int l, int r) {
    seg[id] = {0, 0, 1}; lazy[id] = {-1, 0};
    if (l == r) return;
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void push(int id) {
    if (lazy[id].asgn != -1) seg[id].mn = seg[id].mx = lazy[id].asgn;
    else seg[id].mn += lazy[id].del, seg[id].mx += lazy[id].del;
    if (id*2 < maxN) pass(lazy[id*2], lazy[id]);
    if (id*2+1 < maxN) pass(lazy[id*2+1], lazy[id]);
    lazy[id] = {-1, 0};
}
void update(int id, int l, int r, int findl, int findr, int val, int type) {
    push(id);
    if (r < findl || findr < l) return;
    if (findl <= l && r <= findr) {
        // cout << l << " " << r << " " << val << " " << type << endl;
        thing cur;
        if (type == 1) cur = {val, 0};
        else if (type == 2) cur = {-1, val};
        pass(lazy[id], cur);
        push(id);
        return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, findl, findr, val, type);
    update(id*2+1, mid+1, r, findl, findr, val, type);
    seg[id] = merge(seg[id*2], seg[id*2+1]);
}
node qry(int id, int l, int r, int findl, int findr) {
    push(id);
    if (r < findl || findr < l) return {INF, -INF, 1};
    if (findl <= l && r <= findr) return seg[id];
    int mid = (l+r)/2;
    return merge(qry(id*2, l, mid, findl, findr), qry(id*2+1, mid+1, r, findl, findr));
}
int search1(int id, int l, int r) {
    push(id);
    if (seg[id].sorted) return l;
    int mid = (l+r)/2;
    push(id*2); push(id*2+1);
    if (!seg[id*2].sorted) return search1(id*2, l, mid);
    else return search1(id*2+1, mid+1, r);
}
int search2(int id, int l, int r, int findl, int val) {
    // cout << l << " " << r << " " << findl << endl;
    push(id);
    if (r < findl) return r+1;
    if (l >= findl && seg[id].mx < val) return r+1;
    if (l == r) return r;
    int mid = (l+r)/2;
    push(id*2); push(id*2+1);
    if (l < findl) {
        int ret = search2(id*2, l, mid, findl, val);
        if (ret != mid+1) return ret;
        else {
            int ret2 = search2(id*2+1, mid+1, r, findl, val);
            // cout << mid+1 << " " << r << " " << ret2 << endl;
            return ret2;
            // return search2(id*2+1, mid+1, r, findl, val);
        }
    }
    if (seg[id*2].mx >= val) return search2(id*2, l, mid, findl, val);
    return search2(id*2+1, mid+1, r, findl, val);
}


signed main() {
    ios::sync_with_stdio(0); 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=1;i<=n;i++) a[i] += a[i-1];
    for (int i=1;i<=m;i++) b[i] += b[i-1];
    a[n+1] = INF, b[m+1] = INF;
    for (int i=1;i<=n;i++) {
        int val = upper_bound(b, b+m+1, S[i] - a[i]) - b - 1;
        // cout << S[i] - a[i] << endl;
        if (val != -1) suf[val].push_back({i, P[i]});
        // cout << i << " " << val << endl;
    }
    for (int i=1;i<=m;i++) {
        int val = upper_bound(a, a+n+1, T[i] - b[i]) - a - 1;
        if (val != -1) pre[i].push_back({val, Q[i]});
        // cout << i << " " << val << endl;
    }
    build(1, 0, n);
    // for (int i=1;i<=n;i++) cout << qry(1, 0, n, i, i).mx << endl;
    for (int i=0;i<=m;i++) {
        for (auto [pos, val]:pre[i]) {
            update(1, 0, n, 0, pos, val, 2);
            // for (int j=0;j<=pos;j++) dp[j] += val;
        }
        // for (int j=0;j<=n;j++) cout << qry(1, 0, n, j, j).mn << " "; cout << endl;
        // cout << qry(1, 0, n, 0, 1).sorted << endl;
        // return 0;
        while (!seg[1].sorted) {
            int pos = search1(1, 0, n) - 1, val = qry(1, 0, n, 0, pos).mx;
            int lim = search2(1, 0, n, pos+1, val);
            update(1, 0, n, pos+1, lim, val, 1);
        }
        // for (int j=1;j<=n;j++) dp[j] = max(dp[j-1], dp[j]);
        for (auto [pos, val]:suf[i]) {
            update(1, 0, n, pos, n, val, 2);
            // for (int j=pos;j<=n;j++) dp[j] += val;
            // cout << "suf " << pos << " " << val << endl;
        }
    }
    cout << qry(1, 0, n, n, n).mx << "\n";
}

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