QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#102572 | #5258. Mortgage | fz_zsl# | WA | 1ms | 17712kb | C++14 | 2.6kb | 2023-05-03 14:47:06 | 2023-05-03 14:47:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define LL long long
#define LD long double
#define int LL
#define DB double
#define UI unsigned int
#define N 200005
void cmax(int& a,int b){
(a<b)&&(a=b);
}
void cmin(int& a,int b){
(a>b)&&(a=b);
}
void Read(int& a){
char c=a=0;
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')a=(a*10)+(c^'0'),c=getchar();
}
//void cmin(LL& a,LL b){
// a>b&&(a=b);
//}
bool Bar;
int n,m,l,r,mid,ans,Ans[N],Lim[N];
int top,A[N],s,e,Len[N],len;
LL sum,a,b,Sum[N],Pre[N];
vector<int>St[N],Ed[N];
struct V{
LL x,y;
}Sk[N],tmp;
bool Ka;//real,imag
int Check(V a,V b,V c){
return (a.y-b.y)*(c.x-b.x)<(c.y-b.y)*(a.x-b.x);
}
LL Get_b(int p,int k){
return Sk[p].y-Sk[p].x*k;
}
LL Check(int k){
int l=1,r=top-1,mid;
LL res=Get_b(top,k);
// printf("res:%lld %lld %lld\n",res+sum,Sk[top].x,Sk[top].y+sum);
while(l<=r){
mid=(l+r)>>1;
if(Sk[mid].x>len){
l=mid+1;
// cerr<<"?"<<endl;
continue;
}
a=Get_b(mid,k);
b=Get_b(mid+1,k);
cmin(res,a);
cmin(res,b);
if(b<=a)l=mid+1;
else r=mid-1;
}
return res;
}
signed main() {
// printf("%lf\n",(&Ka-&Bar)/1024.0/1024.0);
freopen("A.in","r",stdin);
// freopen("A.out","w",stdout);
scanf("%lld %lld",&n,&m);
for(int i=1;i<=n;++i)scanf("%lld",&A[i]),Sum[i]=A[i]+Sum[i-1];
for(int i=1;i<=m;++i){
scanf("%lld %lld",&s,&Len[i]);
e=s+Len[i]-1;
St[s].push_back(i);
Ed[n-e+1].push_back(i);
}
for(int i=n;i;--i){
tmp=(V)<%i,-sum%>;
while(top>1&&Check(tmp,Sk[top],Sk[top-1]))--top;
Sk[++top]=tmp,sum+=A[i];
// cerr<<top<<" "<<Sk[top].x<<" "<<Sk[top].y<<endl;
// for(int j=top;j;--j)printf("(%d,%d)%c",Sk[j].x,Sk[j].y," \n"[j==1]);
for(int j:St[i]){
len=Len[j]+i-1,ans=-1;
l=0,r=1e9;
while(l<=r){
mid=(l+r)>>1;
Pre[j]=Sum[len-1]-Sum[i-1];
if(Check(mid)+sum+1ll*mid*(Lim[j]=i-1)>=0)ans=mid,l=mid+1;
else r=mid-1;
}
Ans[j]=ans;
}
}
top=0,sum=0;
for(int l=1,r=n;l<r;++l,--r)swap(A[l],A[r]);
for(int i=n;i;--i){
tmp=(V)<%i-n-1,-sum%>;
while(top>1&&Check(tmp,Sk[top],Sk[top-1]))--top;
Sk[++top]=tmp,sum+=A[i];
// for(int j=top;j;--j)printf("(%d,%d)%c",Sk[j].x,Sk[j].y," \n"[j==1]);
for(int j:Ed[i]){
len=Len[j]+i-1-n-1,ans=-1;
l=0,r=1e9;
// cerr<<"Len:"<<len<<" "<<Sk[top].y+sum+Pre[j]+Sk[top].x*3<<endl;
// exit(0);
while(l<=r){
mid=(l+r)>>1;
if(Check(-mid)+sum+Pre[j]+1ll*mid*Lim[j]>=0)ans=mid,l=mid+1;
else r=mid-1;
}
cmin(Ans[j],ans);
}
}
for(int i=1;i<=m;++i){
if(Ans[i]==-1)puts("stay with parents");
else printf("%lld\n",Ans[i]);
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 17712kb
input:
10 10 21 18 19 18 16 15 13 13 13 10 10 1 6 4 7 3 2 2 6 5 2 6 3 2 4 1 1 5 6 3
output:
result:
wrong answer 1st lines differ - expected: '10', found: ''