Submission #621697

#	Time	Username	Problem	Language	Result	Execution time	Memory
621697		czhang2718	Two Dishes (JOI19_dishes)	C++17	100 / 100	7181 ms	339436 KiB

dishes

#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;
typedef vector<int> vi;
#define f first
#define s second
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i=a; i<=b; i++)

const int N=1e6+1;
int n, m;
ll a[N], b[N], p[N], q[N], s[N], t[N];
map<int,ll> qu[N];

bool st[4*N];
ll seg[4*N];
ll mn[4*N];

void push(int x, int lx, int rx){
    if(rx-lx==1) return;
    if(st[x]){
        seg[2*x+1]=seg[2*x+2]=seg[x];
        st[2*x+1]=st[2*x+2]=1;
        mn[2*x+1]=mn[2*x+2]=seg[x];
        seg[x]=0;
        st[x]=0;
        return;
    }
    seg[2*x+1]+=seg[x];
    seg[2*x+2]+=seg[x];
    mn[2*x+1]+=seg[x];
    mn[2*x+2]+=seg[x];
    seg[x]=0;
}

void add(int l, int r, int x, int lx, int rx, ll v){
    // cout << "add " << l << r << " " << v << "\n";
    push(x, lx, rx);
    if(lx>=l && rx<=r){
        seg[x]+=v;
        mn[x]+=v;
        return;
    }
    if(lx>=r || rx<=l) return;
    int mid=(lx+rx)/2;
    add(l, r, 2*x+1, lx, mid, v);
    add(l, r, 2*x+2, mid, rx, v);
    mn[x]=min(mn[2*x+1], mn[2*x+2]);
}

void add(int l, int r, ll v){
    add(l, r, 0, 0, m+1, v);
}

void assign(int l, int r, ll v, int x, int lx, int rx){
    push(x, lx, rx);
    if(lx>=l && rx<=r){
        // cout << "seg " << lx << " " << rx << " = " << v << "\n";
        seg[x]=v;
        st[x]=1;
        mn[x]=v;
        return;
    }
    if(lx>=r || rx<=l) return;
    int mid=(lx+rx)/2;
    assign(l, r, v, 2*x+1, lx, mid);
    assign(l, r, v, 2*x+2, mid, rx);
    mn[x]=min(mn[2*x+1], mn[2*x+2]);
}

void assign(int l, int r, ll v){
    if(r<=l) return;
    assign(l, r, v, 0, 0, m+1);
}

void assign(int i, ll v){
    assign(i, i+1, v);
}


int walk(ll v, int x, int lx, int rx){
    if(rx-lx==1) return rx;
    push(x, lx, rx);
    int mid=(lx+rx)/2;
    if(mn[2*x+2]<=v) return walk(v, 2*x+2, mid, rx);
    return walk(v, 2*x+1, lx, mid);
}

int walk(ll v){
    return walk(v, 0, 0, m+1);
}

ll qry(int i, int x, int lx, int rx){
    if(rx-lx==1) return mn[x];
    push(x, lx, rx);
    int mid=(lx+rx)/2;
    if(i<mid) return qry(i, 2*x+1, lx, mid);
    return qry(i, 2*x+2, mid, rx);
}
 
ll qry(int i){
    return qry(i, 0, 0, m+1);
}

int main(){
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    ll ans=0;
    vector<vi> pts;
    vector<ll> A(n+1), B(m+1);

    rep(i,1,n){
        cin >> a[i] >> s[i] >> p[i];
        A[i]=A[i-1]+a[i];
    }
    

    A.erase(A.begin());
    rep(i,1,m){
        cin >> b[i] >> t[i] >> q[i];
        B[i]=B[i-1]+b[i];
        int j=upper_bound(all(A), t[i]-B[i])-A.begin();
        if(B[i]<=t[i]) qu[j][i]+=q[i];
    }


    B.erase(B.begin());
    rep(i,1,n){
        int j=upper_bound(all(B), s[i]-A[i-1])-B.begin();
        if(A[i-1]<=s[i]){
            ans+=p[i];
            qu[i-1][j+1]-=p[i];
        }
    }

    rep(i,0,n){
        vector<pii> pts;
        for(auto p:qu[i]) pts.push_back(p);
        reverse(all(pts)); 
        // cout << "x " << i << ":\n";
        for(auto p:pts){
            int y=p.f;
            int v=p.s;
            // cout << y << " " << v << "\n";
            add(y, m+1, v);
            // rep(i,0,m) cout << qry(i) << " ";
            // cout << "\n";
            if(i!=n){
                ll prv=qry(y-1);
                int j=walk(prv); // rightmost <=prv
                assign(y, j, prv);
                // rep(i,0,m) cout << qry(i) << " ";
                // cout << "\n";
            }
        }
    }
    cout << ans+qry(m);
}

// A: (x, <=y)
// B: (x, >=y)

• 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