Submission #170680

#	Time	Username	Problem	Language	Result	Execution time	Memory
170680		puppies_and_rainbows	Two Dishes (JOI19_dishes)	C++14	100 / 100	6209 ms	272368 KiB

dishes

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int inf=100000000000000000;
int it[4100000];
pair<int, int> lazy[4100000];

pair<int, int> merge(pair<int, int> u, pair<int, int> v)
{
    return {u.first+v.first, max(u.second, v.second+u.first)};
}

void down(int id, int l, int r)
{
    it[id]=max(it[id]+lazy[id].first, lazy[id].second);
    if(true)
    {
        lazy[id*2]=merge(lazy[id], lazy[id*2]);
        lazy[id*2+1]=merge(lazy[id], lazy[id*2+1]);
    }
    lazy[id]={0, -inf};
}

void update(int id, int l, int r, int u, int v, pair<int, int> val)
{
    down(id, l, r);
    if(l>v||r<u)
    {
        return;
    }
    if(l>=u&&r<=v)
    {
        lazy[id]=val;
        down(id, l, r);
        return;
    }
    int mid=(l+r)/2;
    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);
    it[id]=max(it[id*2], it[id*2+1]);
}

int get(int id, int l, int r, int pos)
{
    down(id, l, r);
    if(l==r) return it[id];
    int mid=(l+r)/2;
    if(pos<=mid) return get(id*2, l, mid, pos);
    else return get(id*2+1, mid+1, r, pos);
}

int a[1000005], s[1000005], p[1000005];
int b[1000005], t[1000005], q[1000005];
int n, m;
vector<pair<int, int> > events[1000005];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //update(1,0,5,1,5,{1,0});
    //update(1,0,5,1,5,{1,0});
    //cout<<get(1,0,5,4);
    //return 0;
    //freopen("dishes.inp", "r", stdin);
    //freopen("dishes.out", "w", stdout);
    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];
    }
    int dora=0;
    for(int i=1; i<=n; i++)
    {
        int ok=upper_bound(b, b+m+1, s[i]-a[i])-b;
        if(ok>=1)
        {
            events[ok-1].push_back({i, p[i]});
        }
    }
    for(int i=1; i<=m; i++)
    {
        dora+=q[i]; q[i]=-q[i];
        int ok=upper_bound(a, a+n+1, t[i]-b[i])-a;
        if(ok<=n)
        {
            events[i-1].push_back({ok, q[i]});
        }
    }
    fill(lazy, lazy+n*4+5, (pair<int, int>){0, -inf});
    for(int p=0; p<m; p++)
    {
        for(auto i:events[p])
        {
            //cout<<i.first<<" "<<i.second<<endl;
            update(1, 0, n, i.first, n, {i.second, -inf});
        }
        for(auto i:events[p])
        {
            if(i.first)
            {
                //cout<<get(1, 0, n, i.first-1)<<endl;
                update(1, 0, n, i.first, n, {0, get(1, 0, n, i.first-1)});
            }
        }
        for(int i=0; i<=n; i++)
        {
            //cout<<get(1, 0, n, i)<<" ";
        }
        //cout<<endl;
    }
    for(auto i:events[m])
    {
        update(1, 0, n, i.first, n, {i.second, -inf});
    }
    cout<<dora+get(1, 0, n, n);
}

• 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