Submission #1071713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071713		isaachew	Two Dishes (JOI19_dishes)	C++17	100 / 100	5981 ms	448812 KiB

dishes

#include <bits/stdc++.h>

/*
 Why is this Diamond 1?
 Shift segtree and range max
 Too slow for BOJ?
 */
std::pair<long long,long long> combine(std::pair<long long,long long> a,std::pair<long long,long long> b){
    return {a.first+b.first,std::max(a.second+b.first,b.second)};
}
struct segtree{
    int size;
    std::vector<std::pair<long long,long long>> nodes;
    segtree(){}
    void init(int n){
        size=n;
        nodes.resize(2*n-1,{0,0});
    }
    void update(int l,int r,std::pair<long long,long long> tr,int nl,int nr,int ni){
        if(r<=nl||l>=nr)return;
        if(l<=nl&&r>=nr){
            nodes[ni]=combine(nodes[ni],tr);
            return;
        }
        //pushdown
        int nm=(nl+nr)/2;
        nodes[ni+1]=combine(nodes[ni+1],nodes[ni]);
        nodes[ni+2*(nm-nl)]=combine(nodes[ni+2*(nm-nl)],nodes[ni]);
        nodes[ni]={0,-1e18};
        update(l,r,tr,nl,nm,ni+1);
        update(l,r,tr,nm,nr,ni+2*(nm-nl));
    }
    long long query(int p,int nl,int nr,int ni){
        if(nl+1>=nr){
            return nodes[ni].second;//func on 0
        }
        long long othq;
        int nm=(nl+nr)/2;
        if(p<nm){
            othq=query(p,nl,nm,ni+1);
        }else{
            othq=query(p,nm,nr,ni+2*(nm-nl));
        }
        return std::max(othq+nodes[ni].first,nodes[ni].second);
    }
};
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;
    std::cin>>n>>m;
    std::vector<long long> dish1,dish2;
    std::vector<long long> d1sums,d2sums;
    std::vector<std::pair<long long,long long>> d1pts,d2pts;
    std::map<int,std::vector<std::pair<int,long long>>> ndpts;//converted to (max step of dish 2, points)
    std::map<long long,long long> steps1,steps2;
    long long result=0;//constant added
    long long curt=0;
    for(int i=0;i<n;i++){
        long long x,a,b;
        std::cin>>x>>a>>b;
        dish1.push_back(x);
        d1pts.push_back({a,b});
        d1sums.push_back(curt);
        steps1[curt]=i;
        curt+=x;
    }
    d1sums.push_back(curt);
    steps1[curt]=n;
    curt=0;
    for(int i=0;i<m;i++){
        long long x,a,b;
        std::cin>>x>>a>>b;
        dish2.push_back(x);
        d2pts.push_back({a,b});
        d2sums.push_back(curt);
        steps2[curt]=i;
        curt+=x;
    }
    d2sums.push_back(curt);
    steps2[curt]=m;
    for(int i=0;i<n;i++){
        auto maxd2i=steps2.upper_bound(d1pts[i].first-d1sums[i+1]);
        int maxd2=maxd2i==steps2.end()?m:maxd2i->second-1;
        ndpts[i].push_back({maxd2,d1pts[i].second});//(index of step, last index to get affected)
        
    }
    for(int i=0;i<m;i++){
        auto maxd1i=steps1.upper_bound(d2pts[i].first-d2sums[i+1]);
        int maxd1=maxd1i==steps1.end()?n:maxd1i->second-1;
        if(maxd1>=0){
            ndpts[maxd1].push_back({i,-d2pts[i].second});
            result+=d2pts[i].second;
        }
    }
    segtree st;
    st.init(m+1);
    for(int i=0;i<n;i++){
        for(std::pair<int,long long> trans:ndpts[i]){
            st.update(0,trans.first+1,{trans.second,-1e18},0,m+1,0);
        }
        for(std::pair<int,long long> trans:ndpts[i]){
            long long qu=st.query(trans.first,0,m+1,0);
            st.update(trans.first+1,m+1,{0,qu},0,m+1,0);
        }
    }
    std::cout<<st.query(m+1,0,m+1,0)+result<<'\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