Cod sursa(job #1428901)

Utilizator touristGennady Korotkevich tourist Data 5 mai 2015 11:50:42
Problema A+B Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <cstdio>
#define Nmax 100005

using namespace std;

long long dp[Nmax],s[Nmax];
int a[Nmax],st[Nmax],top,maxx[Nmax],n,rmq[Nmax][20];

inline int Lower(long long x)
{
    int st=1,dr=n,mij,sol=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(dp[mij]<x)
        {
            sol=mij; st=mij+1;
        }
        else dr=mij-1;
    }
    return sol;
}

inline long long CMMDC(long long x, long long y)
{
    long long r=x%y;
    while(r)
    {
        x=y; y=r; r=x%y;
    }
    return y;
}

inline void RMQ()
{
    int i,j;
    for(i=1;i<=n;++i) rmq[i][0]=maxx[i];
    for(j=1;(1<<j)<=n;++j)
        for(i=1;i<=n;++i)
            rmq[i][j]=rmq[rmq[i][j-1]][j-1];
}

inline int CB(int poz, long long &x)
{
    long long val=0;
    int pas,poz1=poz;
    for(pas=20;pas>=0;--pas)
    {
        if(rmq[poz1][pas]==0) continue;
        long long aux;
        aux=1LL*(poz-rmq[poz1][pas])*a[rmq[poz1][pas]]-(s[poz]-s[rmq[poz1][pas]])-val;
        if(aux<=x)
        {
            x-=aux; val+=aux;
            poz1=rmq[poz1][pas];
        }
    }
    return poz1;
}

int main()
{
    int T,i,Q,poz,poz1,prv;
    long long x,y;
    freopen ("atlas.in","r",stdin);
    freopen ("atlas.out","w",stdout);
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(i=1;i<=n;++i)
        {
            scanf("%d", &a[i]);
            s[i]=s[i-1]+a[i];
        }
        top=0;
        for(i=1;i<=n;++i) maxx[i]=0;
        for(i=n;i;--i)
        {
            while(top && a[st[top]]<=a[i]) maxx[st[top--]]=i;
            st[++top]=i;
        }
        for(i=1;i<=n;++i)
            if(maxx[i]==i-1) dp[i]=dp[maxx[i]];
            else dp[i]=1LL*(i-maxx[i]-1)*a[i]-(s[i-1]-s[maxx[i]])+dp[maxx[i]];
        //for(i=1;i<=n;++i) printf("%lld ", dp[i]);
        //printf("\n");
        RMQ();
        scanf("%d", &Q);
        while(Q--)
        {
            scanf("%lld", &x);
            poz=Lower(x);
            printf("%d ", poz);
            x-=dp[poz];

            poz1=CB(poz,x);
            //printf("---%d %lld\n", poz1,x);
            if(maxx[poz1]) prv=maxx[poz1];
            else prv=0;
            y=poz-prv;

            long long aa,bb;
            aa=1LL*a[poz1]*y+x;
            bb=y;

            long long d=CMMDC(aa,bb);
            aa/=d; bb/=d;
            printf("%lld/%lld\n", aa,bb);
        }
    }
    return 0;
}