洛谷 P3957 跳房子

https://www.luogu.org/problemnew/show/P3957

错误记录：1.没开longlong 2. -inf不够小

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 #define int ll

 typedef pair<int,int> pii;

 int n,d,K;

 pii p[];

 int qq[],ql,qr;

 int an[];

 //an[i]表示i格子最大得分

 //an[i]=max{an[j]}+s[i],i-r<=j<=i-l

 bool judge(int ttt)

 {

     int l=max(1ll,d-ttt),r=d+ttt;

     ql=;qr=;

     int ans=-0x3f3f3f3f3f3f3f3f,L,R,i;

     an[]=;

     for(i=,L=,R=-;i<=n;i++)

     {

         while(R+<i&&p[R+].fi<=p[i].fi-l)

         {

             ++R;

             while(ql<=qr&&an[qq[qr]]<=an[R])    --qr;

             qq[++qr]=R;

         }

         while(L<i&&p[L].fi<p[i].fi-r)

         {

             if(qq[ql]==L)    ++ql;

             ++L;

         }

         an[i]=ql<=qr?an[qq[ql]]+p[i].se:-0x3f3f3f3f3f3f3f3f;

         ans=max(ans,an[i]);

     }

     return ans>=K;

 }

 signed main()

 {

     int nn,x,y,i;

     scanf("%lld%lld%lld",&nn,&d,&K);

     for(i=;i<=nn;i++)

     {

         scanf("%lld%lld",&x,&y);

         if(!n||x!=p[n].fi)    p[++n].fi=x,p[n].se=y;

         else    p[n].se=max(p[n].se,y);

     }

     int t=;

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

         if(p[i].se>)

             t+=p[i].se;

     if(t<K)

     {

         puts("-1");

         return ;

     }

     int l=,r=1e10,mid;

     while(l!=r)

     {

         mid=l+((r-l)>>);

         if(judge(mid))    r=mid;

         else    l=mid+;

     }

     printf("%lld",l);

     return ;

 }