本蒟蒻没用斜率优化过了此题,但同机房菜鸡瞬间就cha掉了我的sb做法,但他和我都想不出hack数据,求hack。代码如下!
#include<bits/stdc++.h>
#define F(i,j,k) for(register int i=(j);i<=(k);i++)
#define LL long long
using namespace std;
inline char gc(void) {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T> inline void read(T &x) {
T f = 1; x = 0; static char c = gc();
for (; !isdigit(c); c = gc()) if (c == '-') f = -f;
for (; isdigit(c); c = gc()) x = (x << 1) + (x << 3) + (c & 15);
x *= f;
}
char pf[100000], *o1 = pf, *o2 = pf + 100000;
#define ot(x) (o1 == o2 ? fwrite(pf, 1, 100000, stdout), *(o1 = pf) ++= x : *o1 ++= x)
template <class T>
inline void writeln(T x, char c = '\n') {
if (x < 0) ot(45), x = -x;
static char s[25], *b; b = s;
if (!x) *b ++= 48;
for (; x; * b ++= x % 10 + 48, x /= 10);
for (; b-- != s; ot(*b)); ot(c);
}
template <typename T> inline void checkmin(T &a,T b){a=a<b?a:b;}
const int N=1e5+10,M=1e6+10;
const LL INF=1e18;
int n,m,cnt;
LL A,B,C,dp[M],ans=INF;
deque <int> q[N];
struct wzy{int pos,qry,num;LL tim;}a[M*2];
inline LL f(LL x){return A*x*x+B*x+C;}
inline bool cmp(wzy x,wzy y){return (x.tim==y.tim)?x.qry<y.qry:x.tim<y.tim;}
inline void del(int x,LL ti){
while(q[x].size()>1){
int tx=q[x].front();q[x].pop_front();
if(f(ti-a[tx].tim)+dp[a[tx].num]<f(ti-a[q[x].front()].tim)+dp[a[q[x].front()].num]){q[x].push_front(tx);break;}
}
}
inline LL val(int x,LL ti){
if(q[x].empty()){
if(x==1)return f(ti);
else return INF;
}
return f(ti-a[q[x].front()].tim)+dp[a[q[x].front()].num];
}
inline void ins(int x,LL ti,LL tval){
while(!q[x].empty()){
if(f(0)+dp[a[tval].num]<=f(ti-a[q[x].back()].tim)+dp[a[q[x].back()].num])q[x].pop_back();
else break;
}
q[x].push_back(tval);
}
int main(){
//freopen("6302.in","r",stdin);
//freopen("6302.out","w",stdout);
read(n);read(m);read(A);read(B);read(C);
F(i,1,m){
int x,y,p,q;read(x);read(y);read(p);read(q);
++cnt;a[cnt].pos=x;a[cnt].tim=p;a[cnt].qry=1;a[cnt].num=i;
++cnt;a[cnt].pos=y;a[cnt].tim=q;a[cnt].qry=0;a[cnt].num=i;
}
sort(a+1,a+cnt+1,cmp);
F(i,1,cnt)
if(a[i].qry==1){del(a[i].pos,a[i].tim);dp[a[i].num]=val(a[i].pos,a[i].tim);}
else ins(a[i].pos,a[i].tim,i);
F(i,1,cnt)if(a[i].pos==n&&a[i].qry==0){checkmin(ans,dp[a[i].num]+a[i].tim);}
writeln(ans);
fwrite(pf, 1, o1 - pf, stdout);
return 0;
}