(UVA) 1106 - Machine Works [CDQ分治] [DP斜率優化]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=3547

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

//dp[i] = max(dp[j] + r[j] - p[j] + (t[i] - t[j] - 1)*g[j])

typedef long long LL;
typedef __int128 LLL;
const int MAX_N = 1e5 + 6;

struct Mac {
    LL t,p,r,g;
    void input() {
        scanf("%lld %lld %lld %lld",&t,&p,&r,&g);
    }
} mac[MAX_N];

struct Line {
    LLL m,b;
    Line(LL _m,LL _b) {
        m=_m;
        b=_b;
    }
    LLL val(LLL x) {
        return m*x+b;
    }
};

bool operator<(const Mac &m1,const Mac &m2) {
    return m1.t < m2.t;
}

bool operator<(const Line &l1,const Line &l2) {
    return l1.m < l2.m || l1.m==l2.m && l1.b<l2.b;
}

LL dp[MAX_N];

//dp[i] = max(dp[j] + r[j] - p[j] + (t[i] - t[j] + 1)*g[j])

bool check(Line _0,Line _1,Line _2) {
    return (_0.m-_2.m)*(_0.b-_1.b) > (_0.b-_2.b)*(_0.m-_1.m);
}

void do_things(int L,int R) {
    int mid=(L+R)>>1;
    vector<Line> v;
    for (int j=L;mid>=j;j++) {
        if (dp[j] >= mac[j].p) {
            v.push_back(Line(mac[j].g,dp[j]+mac[j].r-mac[j].p+(-mac[j].t-1)*mac[j].g));
        }
    }
    sort(v.begin(),v.end());
    vector<Line> dq;   //use vector as deque XD
    for (Line l:v) {
        while (dq.size()   && dq[dq.size()-1].m == l.m) dq.pop_back();
        while (dq.size()>1 && check(l,dq[dq.size()-1],dq[dq.size()-2])) dq.pop_back();
        dq.push_back(l);
    }
    if (!dq.size()) return;
    int now=0;
    for (int i=mid+1;R>=i;i++) {
        while (now+1<dq.size() && dq[now].val(mac[i].t) < dq[now+1].val(mac[i].t)) now++;
        dp[i] = max(LLL(dp[i]),dq[now].val(mac[i].t));
    }
}

void cdq(int L,int R) {
    if (L==R) return;
    int mid=(L+R)>>1;
    cdq(L,mid);
    do_things(L,R);
    cdq(mid+1,R);
}

int main () {
    int n,c,d;
    int cases=0;
    while (scanf("%d %d %d",&n,&c,&d) != EOF) {
        if (!n && !c && !d) break;
        printf("Case %d: ",++cases);
        for (int i=1;n>=i;i++) {
            mac[i].input();
        }
        memset(dp,0,sizeof(dp));
        mac[0]=Mac{0,0,c,0};
        mac[n+1]=Mac{d+1,0,0,0};
        sort(mac,mac+(n+2));
        cdq(0,n+1);
        printf("%lld\n",dp[n+1]);
    }
}