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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<bits/stdc++.h>
#define ll long long
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define PII pair<int,int>
const int MOD=1000000007;
const int N=100001;
const int M=10000001;
using namespace std;
inline int read(){register char c=getchar();register int s=0,f=1;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())s=(s<<3)+(s<<1)+c-'0';return s*f;}
int n,m,h[N],pos[N][20],a[N],b[N],x;
set<pair<ll,int>>s;
ll d[N][20],da[N][20],db[N][20];
bool cmp(pair<ll,int> a,pair<ll,int> b){return a.first==b.first?h[a.second]<h[b.second]:a.first<b.first;}
int main(){
freopen("in.txt","r",stdin); freopen("out.txt","w",stdout);
n=read();
int LOG=log2(n)+1;
for(int i=1;i<=n;i++) h[i]=read();
s.insert({0x3f3f3f3f3f3f3f3f,0});
s.insert({-0x3f3f3f3f3f3f3f3f,0});
vector<pair<ll,int>>ooo;
for(int i=n;i;i--){
ooo.clear();
auto it=s.lower_bound({h[i],i});
auto ij=it;
for(int j=0;j<=1;j++){
if(ij!=s.end()){
ooo.push_back({abs((ll)h[i]-ij->first),ij->second});
ij++;
}
}
for(int j=0;j<=1;j++){
if(it!=s.begin()){
it--;
ooo.push_back({abs((ll)h[i]-it->first),it->second});
}
}
sort(ooo.begin(),ooo.end(),cmp);
b[i]=ooo[0].second;
a[i]=ooo[1].second;
s.insert({h[i],i});
}
memset(d,0x3f,sizeof d);
for(int i=1;i<=n;i++) {
if(a[i])da[i][1]=abs(h[a[i]]-h[i]);
if(b[a[i]])db[i][1]=abs(h[b[a[i]]]-h[a[i]]);
d[i][1]=da[i][1]+db[i][1];
pos[i][1]=b[a[i]];
}
for(int l=2;l<LOG;l++){
for(int i=1;pos[i][l-1];i++){
if(!pos[pos[i][l-1]][l-1])continue;
d[i][l]=d[i][l-1]+d[pos[i][l-1]][l-1];
da[i][l]=da[i][l-1]+da[pos[i][l-1]][l-1];
db[i][l]=db[i][l-1]+db[pos[i][l-1]][l-1];
pos[i][l]=pos[pos[i][l-1]][l-1];
}
}
x=read();
int ans=0;
double anss=10000000000000000;
for(int i=1;i<=n;i++){
int sa=0,sb=0,k=1,p=i,xx=x;
while(k){
if(xx>=d[p][k])xx-=d[p][k],sa+=da[p][k],sb+=db[p][k],p=pos[p][k],k++;
else k--;
}
if(a[p]&&xx>=abs(h[a[p]]-h[p]))sa+=abs(h[a[p]]-h[p]);
double op=10000000000000000;
if(sb!=0) op=(double)sa/sb;
if(op+0.000001<anss){
anss=op;
ans=i;
}
else if(abs(op-anss)<=0.000001){
if(h[ans]<h[i])ans=i;
}
}
printf("%d\n",ans);
m=read();
while(m--){
int s=read();
x=read();
int sa=0,sb=0,k=1,p=s,xx=x;
while(k){
if(xx>=d[p][k])xx-=d[p][k],sa+=da[p][k],sb+=db[p][k],p=pos[p][k],k++;
else k--;
}
if(a[p]&&xx>=abs(h[a[p]]-h[p]))sa+=abs(h[a[p]]-h[p]);
printf("%d %d\n",sa,sb);
}
return 0;
}
|