2018南京网络赛G

#pragma comment(linker, "/STACK:1024000000,1024000000") 
#include <bits/stdc++.h>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define up rt,rt<<1,rt<<1|1
using namespace std;
typedef long long ll;
const int M = 1e5+7;
const ll inf = 1e18;
int n,q,ans[M*2],p[M<<3],pos;
ll m,a[M*2];
ll mn[M<<3],r[M*2];
void pushup(int rt,int l,int r){
    mn[rt]=min(mn[l],mn[r]);
}
void build(int l,int r,int rt){
    if(l==r){
        mn[rt]=a[l];
        p[rt]=l;
        return ;
    }
    int mid=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(up);
}
void update(int l,int r,int rt){
    if(l==r){
        mn[rt]=inf;
        return ;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) update(lson);
    else update(rson);
    pushup(up);
}
int query(int l,int r,int rt,ll k){
    if(l==r){
        return rt;
    }
    int mid=(l+r)>>1;
    if(mn[rt<<1]<=k) return query(lson,k);
    else return query(rson,k);
}
int main(){
    //freopen("1.in","r",stdin);
    //freopen("1.out","w",stdout);
    scanf("%d%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,n,1);
    ll res=0;ans[0]=0;int tot=0,kkk=-1;
    for(int i=1;i<=100005;i++){
        res+=m;
        if(res<mn[1]){
            ans[i]=ans[i-1];r[i]=res;
        }
        else{
            int tmp=0;
            while(res>=mn[1]){
                int qq=query(1,n,1,res);
                res-=mn[qq];pos=p[qq];
                update(1,n,1);
                tmp++;tot++;
                if(tot==n){
                    kkk=i;
                    break;
                }
            }
            ans[i]=ans[i-1]+tmp;r[i]=res;
        }
        if(kkk!=-1) break;
        //cout<<mn[1]<<endl;
    }
    if(kkk!=-1){//rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrri shit
        for(int i=kkk+1;i<=100005;i++){
            ans[i]=ans[kkk];r[i]=r[kkk];
        }
    }
    scanf("%d",&q);
    while(q--){
        int d;
        scanf("%d",&d);
        printf("%d %lld\n",ans[d],r[d]);
    }
    return 0;
}