Submission #1091737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091737		12345678	Two Dishes (JOI19_dishes)	C++17	100 / 100	2388 ms	197724 KiB

dishes

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=1e6+5;

ll n, m, qsa[nx], qsb[nx], st[nx], tt[nx], p[nx], q[nx], res, tmp;
vector<tuple<ll, ll, ll>> v;

struct segtree
{
    ll d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i];
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int idx, ll vl)
    {
        pushlz(l, r, i);
        if (r<idx||idx<l) return;
        if (l==r) return d[i]=max(d[i], vl), void();
        int md=(l+r)/2;
        update(l, md, 2*i, idx, vl);
        update(md+1, r, 2*i+1, idx, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    void updaterange(int l, int r, int i, int ql, int qr, ll vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l, r, i), void();
        int md=(l+r)/2;
        updaterange(l, md ,2*i, ql, qr, vl);
        updaterange(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
    ll query(int l, int r, int i ,int ql, int qr)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return -1e18;
        if (ql<=l&&r<=qr) return d[i];
        int md=(l+r)/2;
        return max(query(l, md, 2*i, ql, qr), query(md+1, r, 2*i+1, ql, qr));
    }
} s;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m;
    for (int i=1; i<=n ;i++) cin>>qsa[i]>>st[i]>>p[i], qsa[i]+=qsa[i-1];
    for (int i=1; i<=m; i++) cin>>qsb[i]>>tt[i]>>q[i], qsb[i]+=qsb[i-1];
    for (int i=1; i<=n; i++)
    {
        if (st[i]<qsa[i]) continue;
        ll x=upper_bound(qsb, qsb+m+1, st[i]-qsa[i])-qsb-1;
        if (x!=m) v.push_back({i-1, -(x+1), p[i]});
        res+=p[i];
    }
    for (int i=1; i<=m; i++)
    {
        if (tt[i]<qsb[i]) continue;
        ll x=upper_bound(qsa, qsa+n+1, tt[i]-qsb[i])-qsa-1;
        if (x==n) res+=q[i];
        else v.push_back({x, -i, -q[i]});
    }
    sort(v.begin(), v.end());
    s.updaterange(0, m, 1, 1, m, -1e18);
    for (auto [x, y, vl]:v) 
    {
        y=-y, vl=-vl;
        //cout<<"point "<<x<<' '<<y<<' '<<vl<<'\n';
        tmp=s.query(0, m, 1, 0, y);
        s.update(0, m, 1, y, tmp);
        s.updaterange(0, m, 1, y, m, vl);
    }
    cout<<res+s.query(0, m, 1, 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