Submission #1070093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070093		heeew	Two Dishes (JOI19_dishes)	C++14	74 / 100	3131 ms	245152 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=1.557e+18;

struct Seg
{
    lint sum;
    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].sum+=seg[i].sum;
    seg[i<<1|1].sum+=seg[i].sum;
    seg[i<<1].setv(seg[i].v,seg[i].lazy);
    seg[i<<1|1].setv(seg[i].v,seg[i].lazy);
    seg[i].sum=0;
    seg[i].v=min(seg[i<<1].v,seg[i<<1|1].v);
    seg[i].lazy=0;
}

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

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,int t)
{
    if(s>x || e<=x)return 0;
    if(s==x && x+1==e)return seg[i].v+seg[i].sum*t;
    update_lazy(i);
    return find_(i<<1,s,(s+e)>>1,x,t)+find_(i<<1|1,(s+e)>>1,e,x,t);
}

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);
        update_sum(1,0,n+1,i,n+1,s1[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;
        lint cut=-INF;
        update_(1,0,n+1,0,ci[i],s2[i],cut);
        cutted.push_back(ci[i]);
        for(auto j : endp[i])
        {
            update_sum(1,0,n+1,j,n+1,-s1[j]);
            update_(1,0,n+1,j,n+1,s1[j],cut);
            cutted.push_back(j);
        }
        sort(cutted.begin(),cutted.end());
        for(auto p : cutted)
        {
            if(!p)continue;
            cut=find_(1,0,n+1,p-1,0);
            update_(1,0,n+1,p,n+1,0,cut);
        }
        cutted.clear();
    }
    cout << find_(1,0,n+1,n,1);
    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: 0 / 17
• Subtask 8: 0 / 9