QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#130248#5258. Mortgagestefanbalaz2222RE 0ms0kbC++142.6kb2023-07-23 18:50:322023-07-23 18:50:33

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-23 18:50:33]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-07-23 18:50:32]
  • 提交

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

output:


result: