RT。斜率优化，WA on 15 求助 /kel

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <iostream>

#define N 500010
#define int long long

int dp[N];
int n,m,A,B,C;
int x[N],y[N],p[N],q[N];
struct Thing
{
    int op,id,tim;
    bool operator < (const Thing &bb)const
    {
        return tim != bb.tim ? tim < bb.tim : op > bb.op;
    }
}t[N << 1];
int opcnt;
std::vector <int> v[N];

int k0;

int Y(int k)
{
	return dp[k] + A * q[k] * q[k] - B * q[k];
}

int X(int k)
{
	return q[k];
}

bool a_better_b(int a,int b)
{
	return k0 * (X(b) - X(a)) < (Y(b) - Y(a));
}

double K(int a,int b)
{
	return (1.0 * (Y(a) - Y(b))) / (1.0 * (X(a) - X(b))); 
}

int ans = 1926081700000000ll;
signed main()
{
    scanf("%lld%lld%lld%lld%lld",&n,&m,&A,&B,&C);
    for(int i = 1;i <= m;i++)
    {
        scanf("%lld%lld%lld%lld",&x[i],&y[i],&p[i],&q[i]);
		t[++opcnt] = (Thing){0,i,p[i]};
		t[++opcnt] = (Thing){1,i,q[i]};
    }
	std::sort(t + 1,t + 1 + opcnt);
	v[1].push_back(0);
	for(int T = 1;T <= opcnt;T++)
	{
		if(t[T].op == 0)
		{
			int i = t[T].id;
			k0 = 2 * A * p[i];
			if(v[x[i]].size() == 0)
			{
				dp[i] = -1;
				continue;
			}
			int l = 0,r = v[x[i]].size() - 2;
			int j = -0x3f3f3f3f,mid;
			while(l <= r)
			{
				mid = l + r >> 1;
				if(a_better_b(v[x[i]][mid],v[x[i]][mid + 1]))
					r = mid - 1,j = v[x[i]][mid];
				else
					l = mid + 1;
			}
			if(j == -0x3f3f3f3f)
				j = v[x[i]][v[x[i]].size() - 1];
			dp[i] = dp[j] + A * (p[i] - q[j]) * (p[i] - q[j]) + B * (p[i] - q[j]) + C;
			if(y[i] == n)
			    ans = std::min(ans,dp[i] + q[i]);
		}
		else
		{
			int i = t[T].id;
			if(dp[i] == -1)
			    continue;
			int now = v[y[i]].size() - 1;
			while(now >= 1 && K(v[y[i]][now - 1],v[y[i]][now]) >= K(v[y[i]][now],i))
			{
				v[y[i]].pop_back(),now--;
			}
			v[y[i]].push_back(i);
		}
	}
	printf("%lld\n",ans);
	return 0;
}