BZOJ3613 HEOI2014南园满地堆轻絮

时间：2021-06-19 22:10:01

　　不明白在某谷上是怎么标到紫的。二分答案或者发现答案就是最大逆序差的一半。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 5000010

int n,a[N],P,w,x,y,z;

int f(int t){return ((1ll*w*t%P*t%P*t%P+1ll*x*t%P*t%P)%P+(1ll*y*t%P+z)%P)%P;}

bool check(int x)

{

    int last=;

    for (int i=;i<=n;i++)

    if (a[i]>=last) last=max(last,a[i]-x);

    else if (last-a[i]>x) return ;

    return ;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj3613.in","r",stdin);

    freopen("bzoj3613.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),w=read(),x=read(),y=read(),z=read(),a[]=read(),P=read();

    for (int i=;i<=n;i++)

    a[i]=(f(a[i-])+f(a[i-]))%P;

    int l=,r=P,ans=;

    while (l<=r)

    {

        int mid=l+r>>;

        if (check(mid)) ans=mid,r=mid-;

        else l=mid+;

    }

    cout<<ans;

    return ;

}

相关文章