Submission #1070223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070223		heeew	Two Dishes (JOI19_dishes)	C++14	100 / 100	2597 ms	225612 KiB

dishes

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;

const int MAX_N=1000010;
const lint INF=2.1e+15;

struct Seg
{
    lint v,lazy;
    void setv(lint vp,lint lp)
    {
        v=max(v+lp,vp);
        lazy+=lp;
    }
};

int n,m;
lint t1[MAX_N],t2[MAX_N],c1[MAX_N],c2[MAX_N],s1[MAX_N],s2[MAX_N];
lint ts1[MAX_N],ts2[MAX_N],ci[MAX_N];
Seg seg[MAX_N<<2];
vint endp[MAX_N];

void update_lazy(int i)
{
    seg[i<<1].setv(seg[i].v,seg[i].lazy);
    seg[i<<1|1].setv(seg[i].v,seg[i].lazy);
    seg[i].v=-INF;
    seg[i].lazy=0;
}

void update_(int i,int s,int e,int l,int r,lint add,lint cut)
{
    if(s>=r || e<=l)return;
    if(l<=s && e<=r)
    {
        seg[i].setv(cut,add);
        return;
    }
    update_lazy(i);
    update_(i<<1,s,(s+e)>>1,l,r,add,cut);
    update_(i<<1|1,(s+e)>>1,e,l,r,add,cut);
}

lint find_(int i,int s,int e,int x)
{
    if(s>x || e<=x)return 0;
    if(s==x && x+1==e)return seg[i].v;
    update_lazy(i);
    return find_(i<<1,s,(s+e)>>1,x)+find_(i<<1|1,(s+e)>>1,e,x);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        cin >> t1[i] >> c1[i] >> s1[i];
        ts1[i]=t1[i]+ts1[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        cin >> t2[i] >> c2[i] >> s2[i];
        ts2[i]=t2[i]+ts2[i-1];
    }
    for(int i=1;i<=n;i++)
    {
        int p=upper_bound(ts2,ts2+m+1,c1[i]-ts1[i])-ts2;
        if(!p)continue;
        endp[p].push_back(i);
    }
    for(int i=1;i<=m;i++)
        ci[i]=upper_bound(ts1,ts1+n+1,c2[i]-ts2[i])-ts1;
    for(int i=1;i<=m;i++)
    {
        vint cutted;
        update_(1,0,n+1,0,ci[i],s2[i],-INF);
        cutted.push_back(ci[i]);
        for(auto j : endp[i])
        {
            update_(1,0,n+1,j,n+1,s1[j],-INF);
            cutted.push_back(j);
        }
        sort(cutted.begin(),cutted.end());
        for(auto p : cutted)
            if(p)
                update_(1,0,n+1,p,n+1,0,find_(1,0,n+1,p-1));
        cutted.clear();
    }
    for(auto j : endp[m+1])
        update_(1,0,n+1,j,n+1,s1[j],-INF);
    cout << find_(1,0,n+1,n);
    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: 17 / 17
• Subtask 8: 9 / 9