Submission #963963

#	Time	Username	Problem	Language	Result	Execution time	Memory
963963		Tuanlinh123	Two Dishes (JOI19_dishes)	C++17	100 / 100	4530 ms	248564 KiB

dishes

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
 
const ll maxn=1000005, inf=1e18;
namespace SegTree
{
    ll n;
    struct Node
    {
        ll Min, lzs, lza;

        inline void act(ll a, ll s)
        {
            Min+=s, (lza==inf?lzs:lza)+=s;
            if (a!=inf) Min=lza=a, lzs=0;
        }
    } St[maxn*4];

    void Move(ll i)
    {
        if (St[i].lza!=inf)
        {
            ll t=St[i].lza; St[i].lza=inf;
            St[i*2].lza=St[i*2].Min=t, St[i*2].lzs=0;
            St[i*2+1].lza=St[i*2+1].Min=t, St[i*2+1].lzs=0;
        }
        else if (St[i].lzs)
        {
            ll t=St[i].lzs; St[i].lzs=0;
            (St[i*2].lza==inf?St[i*2].lzs:St[i*2].lza)+=t, St[i*2].Min+=t;
            (St[i*2+1].lza==inf?St[i*2+1].lzs:St[i*2+1].lza)+=t, St[i*2+1].Min+=t;
        }
    }

    void update(ll i, ll Start, ll End, ll l, ll r, ll a, ll s)
    {
        if (Start>=l && End<=r) {St[i].act(a, s); return;}
        ll mid=(Start+End)/2; Move(i);
        if (mid>=l) update(i*2, Start, mid, l, r, a, s);
        if (mid+1<=r) update(i*2+1, mid+1, End, l, r, a, s);
        St[i].Min=min(St[i*2].Min, St[i*2+1].Min);
    }
    void add(ll l, ll r, ll v) {update(1, 0, n, l, r, inf, v);}
    void ass(ll l, ll r, ll v) {update(1, 0, n, l, r, v, 0);}

    ll Find(ll i, ll Start, ll End, ll idx, ll v)
    {
        if (Start==End) return Start;
        ll mid=(Start+End)/2; Move(i);
        if (mid+1<=idx || St[i*2+1].Min<=v) 
            return Find(i*2+1, mid+1, End, idx, v);
        return Find(i*2, Start, mid, idx, v);
    }
    ll Find(ll idx, ll v) {return Find(1, 0, n, idx, v);}

    ll query(ll i, ll Start, ll End, ll idx)
    {
        if (Start==End) return St[i].Min;
        ll mid=(Start+End)/2; Move(i);
        if (mid>=idx) return query(i*2, Start, mid, idx);
        return query(i*2+1, mid+1, End, idx);
    }
    ll query(ll idx){return query(1, 0, n, idx);}
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll n, m, sum=0; cin >> n >> m, SegTree::n=m;
    vector <ll> a(n), s(n), p(n), b(m), t(m), q(m);
    vector <vector <pll>> H(n);
    for (ll i=0; i<n; i++) cin >> a[i] >> s[i] >> p[i];
    for (ll j=0; j<m; j++) cin >> b[j] >> t[j] >> q[j];
    for (ll i=1; i<n; i++) a[i]+=a[i-1];
    for (ll i=1; i<m; i++) b[i]+=b[i-1];
    for (ll i=0; i<n; i++)
    {
        if (s[i]-a[i]<0) continue; sum+=p[i];
        ll pos=lower_bound(b.begin(), b.end(), s[i]-a[i]+1)-b.begin();
        if (pos<m) H[i].pb({pos+1, -p[i]});
    }
    for (ll i=0; i<m; i++)
    {
        if (t[i]-b[i]<0) continue;
        ll pos=lower_bound(a.begin(), a.end(), t[i]-b[i]+1)-a.begin();
        if (pos<n) H[pos].pb({i+1, q[i]});
        else sum+=q[i];
    }
    SegTree::ass(0, m, sum);
    for (ll i=0; i<n; i++)
    {
        vector <pll> range, r;
        sort(H[i].begin(), H[i].end());
        for (auto [p, w]:H[i])
        {
            SegTree::add(p, m, w);
            if (!sz(range) || range.back().fi!=p)
                range.pb({p, w});
            else range.back().se+=w;
        }
        range.pb({m+1, 0});
        for (ll j=0, sum=0; j<sz(range); j++)
            r.pb({range[j].fi-1, sum}), sum+=range[j].se;
        vector <ll> mi(sz(r), -inf);
        for (ll j=1; j<sz(mi); j++)
            mi[j]=max(mi[j-1], SegTree::query(r[j-1].fi));
        for (ll j=sz(mi)-1; j>=0; j--)
        {
            ll st=j?r[j-1].fi+1:0;
            if (SegTree::query(st)>=mi[j]) continue;
            SegTree::ass(st, SegTree::Find(st, mi[j]), mi[j]);
        }
        // for (ll j=0; j<=m; j++) cout << SegTree::query(j) << " "; cout << "\n";
    }
    cout << SegTree::query(m);
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:87:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   87 |         if (s[i]-a[i]<0) continue; sum+=p[i];
      |         ^~
dishes.cpp:87:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   87 |         if (s[i]-a[i]<0) continue; sum+=p[i];
      |                                    ^~~

• 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