QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#130248 | #5258. Mortgage | stefanbalaz2222 | RE | 0ms | 0kb | C++14 | 2.6kb | 2023-07-23 18:50:32 | 2023-07-23 18:50:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define ll long long
typedef pair<int,int> pii;
int mod=1000000+7;
const double dmod=(double)1/mod;
inline int add(int x,int y){int ret=x+y;if(ret>=mod)ret-=mod;return ret;}
inline int sub(int x,int y){int ret=x-y;if(ret<0)ret+=mod;return ret;}
inline int mul(int x,int y){return ((ll)x*y)%mod;}
inline int step(int base,int pw){int ret=1;while(pw){if(pw&1)ret=mul(ret,base);base=mul(base,base);pw>>=1;}return ret;}
inline int invv(int x){return step(x,mod-2);}
const int maxn=2e5+10;
ll p[maxn],a[maxn],inf=1e18;
int n,q;
struct line{
ll a,b;
ll eval(ll x){
return a*x+b;
}
};
vector<line> tree[maxn*4];
double intersect(line c1,line c2){
return ((double)c2.b-c1.b)/((double)c1.a-c2.a);
}
void append(vector<line>&v,line c){
while(v.size() && intersect(v.back(),c)<0)v.pop_back();
while(v.size()>=2 && intersect(v[v.size()-2],v[v.size()-1])>=intersect(v[v.size()-2],c))v.pop_back();
v.pb(c);
}
void build(int x,int l,int r){
if(l==r)return;
int mid=(l+r)/2;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
tree[x]=tree[x*2];
for(int i=0;i<tree[x*2+1].size();i++){
append(tree[x],tree[x*2+1][i]);
}
}
ll go(vector<line>&v,ll x){
int l=0;
int r=v.size()-1;
int sr,ret=-1;
while(l<=r){
sr=(l+r)/2;
ll inter=inf;
if(sr<v.size()-1)inter=intersect(v[sr],v[sr+1]);
if(x<=inter){
r=sr-1;
ret=sr;
}
else l=sr+1;
}
return v[ret].eval(x);
}
ll qry(int x,int l,int r,int lp,int rp,ll val){
if(l>rp || r<lp)return inf;
if(l>=lp && r<=rp){
return go(tree[x],val);
}
int mid=(l+r)/2;
return min(qry(x*2,l,mid,lp,rp,val),qry(x*2+1,mid+1,r,lp,rp,val));
}
int main() {
//freopen("test.txt","r",stdin);
//freopen("moj.txt","w",stdout);
scanf("%d %d",&n,&q);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
p[i]=p[i-1]+a[i];
}
build(1,1,n);
while(q--){
int lp,rp;
scanf("%d %d",&lp,&rp);
rp=lp+rp-1;
ll l=0;
ll r=1e9;
ll x=-1;
ll sr;
while(l<=r){
sr=(l+r)/2;
ll pom=qry(1,1,n,lp,rp,sr);
if(pom-p[lp-1]+(lp-1)*sr>=0){
l=sr+1;
x=sr;
}
else r=sr-1;
}
if(x<0)printf("stay with parents\n");
else printf("%lld\n",x);
}
return 0;
}
詳細信息
Test #1:
score: 0
Runtime Error
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