Pagini recente » Cod sursa (job #2451535) | Cod sursa (job #3216924) | Cod sursa (job #1490549) | Cod sursa (job #1498026) | Cod sursa (job #1428901)
#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;
}