Public feed
#601031
#include<iostream>#include<string>#include<vector>#include<cmath>#include<cstdio>#include<algorithm>using namespace std;double num[250000];double min8[50000];double min64[7000];double min512[4000];double min4096[600];double min32768[50];double min65536[20];double min75000[10];double min125000[5];//double min2048[8000];//double min128[;vector<double> min32;double min16384[100];int Mn=pow(2.0,50.0);int m1=0,m2=0,m3=0,m4=0,m5=0,m6=0,m7=0,m8=0,m9=0;double minelement(double arr[],int x,int y){ double mi=arr[x]; for(int i=x+1;i<y;i++) { if(mi>arr[i]) mi=arr[i]; // cout<<arr[i]<<endl; } // cout<<mi<<endl; return mi;} double minimum8(int x,int y){ //cout<<x<<" "<<y<<endl; if((y-x)<16) return minelement(num,x,y); // cout<<"hi"<<endl; int st,end; double min=pow(2.0,50.0); st=(int)ceil(x*1.0/8.0); end=(int)floor(y*1.0/8.0); int tst=st; int tend=end; double m=minelement(min8,st,end); min=m; st=x; end=tst*8; m=minelement(num,st,end); if(m<min) min=m; st=tend*8; end=y; if(st<end) { m=minelement(num,st,end); if(m<min) min=m; } return min;} double minimum64(int x,int y){ if((y-x)<128) return minimum8(x,y); int st,end; double min=pow(2.0,50.0); st=(int)ceil(x*1.0/64.0); end=(int)floor(y*1.0/64.0); int tst=st; int tend=end; double m=minelement(min64,st,end); min=m; st=x; end=tst*64; m=minimum8(st,end); if(m<min) min=m; st=tend*64; end=y; if(st<end) { m=minimum8(st,end); if(m<min) min=m; } return min;} double minimum512(int x,int y){ if((y-x)<1024) return minimum64(x,y); int st,end; double min=pow(2.0,50.0); st=(int)ceil(x*1.0/512.0); end=(int)floor(y*1.0/512.0); int tst=st; int tend=end; double m=minelement(min512,st,end); min=m; st=x; end=tst*512; m=minimum64(st,end); if(m<min) min=m; st=tend*512; end=y; if(st<end) { m=minimum64(st,end); if(m<min) min=m; } return min;} double minimum4096(int x,int y){ if((y-x)<8192) return minimum512(x,y); int st,end; double min=pow(2.0,50.0); st=(int)ceil(x*1.0/4096.0); end=(int)floor(y*1.0/4096.0); int tst=st; int tend=end; double m=minelement(min4096,st,end); min=m; st=x; end=tst*4096; m=minimum512(st,end); if(m<min) min=m; st=tend*4096; end=y; if(st<end) { m=minimum512(st,end); if(m<min) min=m; } return min;} double minimum32768(int x,int y){ if((y-x)<65536) return minimum4096(x,y); int st,end; double min=pow(2.0,50.0); st=(int)ceil(x*1.0/32768.0); end=(int)floor(y*1.0/32768.0); int tst=st; int tend=end; double m=minelement(min32768,st,end); min=m; st=x; end=tst*32768; m=minimum4096(st,end); if(m<min) min=m; st=tend*32768; end=y; if(st<end) { m=minimum4096(st,end); if(m<min) min=m; } return min;} double minimum65536(int x,int y){ if((y-x)<131072) return minimum32768(x,y); int st,end; double min=pow(2.0,50.0); st=(int)ceil(x*1.0/65536.0); end=(int)floor(y*1.0/65536.0); int tst=st; int tend=end; double m=minelement(min65536,st,end); min=m; st=x; end=tst*65536; m=minimum32768(st,end); if(m<min) min=m; st=tend*65536; end=y; if(st<end) { m=minimum32768(st,end); if(m<min) min=m; } return min;} double minimum75000(int x,int y){ if((y-x)<150000) return minimum65536(x,y); int st,end; double min=pow(2.0,50.0); st=(int)ceil(x*1.0/75000.0); end=(int)floor(y*1.0/75000.0); int tst=st; int tend=end; double m=minelement(min75000,st,end); min=m; st=x; end=tst*75000; m=minimum65536(st,end); if(m<min) min=m; st=tend*75000; end=y; if(st<end) { m=minimum65536(st,end); if(m<min) min=m; } return min;} double minimum125000(int x,int y){ if((y-x)<250000) return minimum75000(x,y); int st,end; double min=pow(2.0,50.0); st=(int)ceil(x*1.0/125000.0); end=(int)floor(y*1.0/125000.0); int tst=st; int tend=end; double m=minelement(min125000,st,end); min=m; st=x; end=tst*125000; m=minimum75000(st,end); if(m<min) min=m; st=tend*125000; end=y; if(st<end) { m=minimum75000(st,end); if(m<min) min=m; } return min;} int main(){ //vector<double> num; int n; float k; cin>>n; int flag[8]; double minim[8]; if(n){ cin>>k; num[m1++]=k; } for(int i=0;i<8;i++) { flag[i]=1; minim[i]=k; } for(int i=1;i<n;i++) { scanf("%f",&k); if(i%125000==0) {min125000[m2++]=(minim[7]); flag[7]=0; } if(i%75000==0) { min75000[m3++]=(minim[6]); flag[6]=0; } if(i%65536==0) { min65536[m4++]=(minim[5]); flag[5]=0; } if(i%32768==0) { min32768[m5++]=(minim[4]); flag[4]=0;} if(i%4096==0) { min4096[m6++]=(minim[3]); flag[3]=0;} if(i%512==0) { min512[m7++]=(minim[2]); flag[2]=0;} if(i%64==0) { min64[m8++]=(minim[1]); flag[1]=0;} if(i%8==0) { min8[m9++]=(minim[0]); flag[0]=0;} for(int j=0;j<8;j++) { if(flag[j]==0) { minim[j]=k; flag[j]=1; } else if(minim[j]>k) minim[j]=k; } num[m1++]=k; } if(n%125000==0) {min125000[m2++]=(minim[7]); flag[7]=0; } if(n%75000==0) { min75000[m3++]=(minim[6]); flag[6]=0; } if(n%65536==0) { min65536[m4++]=(minim[5]); } if(n%32768==0) { min32768[m5++]=(minim[4]); } if(n%4096==0) { min4096[m6++]=(minim[3]); } if(n%512==0) { min512[m7++]=(minim[2]); } if(n%64==0) { min64[m8++]=(minim[1]); } if(n%8==0) { min8[m9++]=(minim[0]); } //cout<<endl; cin>>k; for(int i=0;i<k;i++) { int x,y; scanf("%d %d",&x,&y); printf("%0.6f\n",minimum75000(x,y)); } // cin>>n; return 0;}