oj.uz

Submission #1070128

# Submission time Handle Problem Language Result Execution time Memory
1070128 2024-08-22T11:48:28 Z urd05 Two Dishes (JOI19_dishes) C++17
0 / 100
 616 ms 77684 KB 
#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 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)
{  
  update_lazy(i);
    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)
{
  update_lazy(i);
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 77076 KB Output is correct
2 Incorrect 597 ms 77684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Incorrect 5 ms 39516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Incorrect 5 ms 39516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Incorrect 5 ms 39516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Incorrect 5 ms 39516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 39516 KB Output is correct
2 Correct 5 ms 39516 KB Output is correct
3 Incorrect 5 ms 39516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 77076 KB Output is correct
2 Incorrect 597 ms 77684 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 616 ms 77076 KB Output is correct
2 Incorrect 597 ms 77684 KB Output isn't correct
3 Halted 0 ms 0 KB -