1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
typedef long long LL;
#define clr(x) memset((x),0,sizeof(x))
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 100050;
int s[maxn],s2[maxn];
int l,r;
int l2,r2;
int t,n;
LL R;
LL a[maxn];
int main()
{
scanf("%d",&t);
int cas = 0;
while(t--)
{
scanf("%d%lld",&n,&R);
for(int i = 1;i<=n;i++)
scanf("%lld",&a[i]);
l = r = 0;
l2= r2=0;
s[r++] = 1;
pair <int,int > ans = make_pair(inf,inf);
LL res=0;
for(int i = 2;i<=n;i++)
{
if(res<a[s[l]]+a[i] + (i-s[l])*R)
{
res = a[s[l]] +a[i] +(i-s[l])*R;
ans = make_pair(s[l],i);
}
else if(s[l]<ans.first&&res == a[s[l]]+a[i]+(i-s[l])*R)
{
ans = make_pair(s[l],i);
}
while(l<r&&a[i]-i*R >a[s[r-1]]-s[r-1]*R) r--;
s[r++] = i;
while(l<r&&s[l]<=i-n/2) l++;
if(i==n/2+1)
{
s2[r2++] = 1;
}
if(i>n/2+1)
{
if(res<a[s2[l2]]+a[i]+(s2[l2]+n-i)*R)
{
res = a[s2[l2]] +a[i] +(s2[l2]+n-i)*R;
ans = make_pair(s2[l2],i);
}
else if(s2[l2]<ans.first&&res==a[s2[l2]]+a[i]+(s2[l2]+n-i)*R)
{
ans = make_pair(s2[l2],i);
}
while(l2<r2&&a[i-n/2]+(i-n/2)*R>a[s2[r2-1]]+s2[r2-1]*R) r2--;
s2[r2++] = i-n/2;
}
}
printf("Case #%d:\n",++cas);
printf("%d %d\n",ans.first,ans.second);
}
return 0;
}
|