fork download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int N = 1<<17;
  7.  
  8. struct query {
  9.     unsigned l,r,block,idx;
  10.     bool operator <(const query &a) const {
  11.         return ((block==a.block) ? ((block&1) ? (r<a.r) : (r>a.r)) : (block<a.block));
  12.     }
  13. };
  14.  
  15. template < typename T >
  16. struct fenwick_tree {
  17.     int n;
  18.     T *it;
  19.     void initialize(int k) {
  20.         int i;
  21.         n=k;
  22.         delete [] it;
  23.         it=(T*)malloc((sizeof(T)*(n+1)));
  24.         for(i=1;i<=n;i++) it[i]=0;
  25.     }
  26.     void update(int pos, T val) {
  27.         for(;pos<=n;pos+=pos&(-pos)) it[pos]+=val;
  28.     }
  29.     T query(int pos) {
  30.         T ans=0;
  31.         for(;pos>0;pos-=pos&(-pos)) ans+=it[pos];
  32.         return ans;
  33.     }
  34.     T query(int l, int r) {
  35.         return query(r)-query(l-1);
  36.     }
  37. };
  38.  
  39.  
  40. int tests,current_case;
  41. query queries[N];
  42. int n,q,a[N];
  43. fenwick_tree < long long > sum,cnt;
  44. int sz;
  45. int l,r;
  46. unsigned sq;
  47. double answer[N];
  48. long long s;
  49. long long ps[N];
  50.  
  51. void message(int current_case) {
  52.     fprintf(stderr, "Case %d solved!\n", current_case);
  53. }
  54.  
  55. void add_it(int value) {
  56.     ++sz;
  57.     sum.update(value,value);
  58.     cnt.update(value,1);
  59.     s+=value*1ll*cnt.query(1,value);
  60.     s+=sum.query(value+1,100000);
  61. }
  62.  
  63. void remove_it(int value) {
  64.     --sz;
  65.     s-=value*1ll*cnt.query(1,value);
  66.     s-=sum.query(value+1,100000);
  67.     sum.update(value,-value);
  68.     cnt.update(value,-1);
  69. }
  70.  
  71. double get_answer() {
  72.     long long all=sz*1ll*sz,sum=(s-(ps[r]-ps[l-1]))*2+ps[r]-ps[l-1];
  73.     return (double)(sum)/(double)(all);
  74. }
  75.  
  76. int main() {
  77.     int i;
  78.  
  79.     tests=1;
  80.     for(current_case=1;current_case<=tests;current_case++) {
  81.         scanf("%d %d", &n, &q);
  82.         for(i=1;i<=n;i++) scanf("%d", &a[i]),ps[i]=ps[i-1]+a[i];
  83.         sum.initialize(100000);
  84.         cnt.initialize(100000);
  85.         sq=sqrt(n);
  86.         for(i=1;i<=q;i++) {
  87.             scanf("%u %u", &queries[i].l, &queries[i].r);
  88.             queries[i].idx=i;
  89.             queries[i].block=queries[i].l/sq;
  90.         }
  91.         sort(queries+1,queries+1+q);
  92.         l=queries[1].l;
  93.         r=queries[1].r;
  94.         for(i=l;i<=r;i++) add_it(a[i]);
  95.         for(i=1;i<=q;i++) {
  96.             while(r<queries[i].r) ++r,add_it(a[r]);
  97.             while(l<queries[i].l) remove_it(a[l]),++l;
  98.             while(l>queries[i].l) --l,add_it(a[l]);
  99.             while(r>queries[i].r) remove_it(a[r]),--r;
  100.             answer[queries[i].idx]=get_answer();
  101.         }
  102.         for(i=1;i<=q;i++) printf("%.10lf\n", answer[i]);
  103.         message(current_case);
  104.     }
  105.  
  106.     return 0;
  107. }
Time limit exceeded #stdin #stdout 5s 9648KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/mLPdHg
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!