CSES - HIIT Open 2016 - Results
Submission details
Task:Approximate
Sender:Anonyymit Algoritmistit
Submission time:2016-05-28 14:14:51 +0300
Language:C++
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.43 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:32:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < S.size(); ++j) {
                              ^
input/code.cpp:15:10: warning: unused variable 'dn' [-Wunused-variable]
   double dn = n;
          ^

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; 

int kek[101][101010];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  
  int n, q;
  
  cin >> n >> q;
  
  double dn = n;
  
  vector<int> S;
  vector<int> sums;
  
  double sum = 0;
  for (int i = 0; i < n; ++i) {
    int t;
    cin >> t;
    S.push_back(t);
    sums.push_back(sum);
    sum += t;
  }
  sums.push_back(sum);
  cout << fixed << setprecision(6);
  
  kek[S[0]][0]++;
  for (int j = 1; j < S.size(); ++j) {
    for (int i = 1; i < 101; ++i)
      kek[i][j] = kek[i][j-1];
    kek[S[j]][j]++;
  }
  
  for (int i = 0; i < q; ++i) {
    int a, b;
    cin >> a >> b;
    double s = sums[b]-sums[a-1];
    double m = (b-a+1);
    double c = s/m;
    
    /*
    double err = 0;
    for (int j = a; j <= b; ++j) {
      double t = S[j-1] - c;
      err += t*t;
    }
    */
    
    double err = 0;
    for (int j = 1; j < 101; ++j) {
      int count = 0;
      if (a == 1) count = kek[j][b-1];
      else count = kek[j][b-1] - kek[j][a-2];
      if (count > 0) {
	double t = ((double)j - c);
	err += ((double)count)*t*t;
      }
    }
    cout << err/m << endl;
  }
  
}

Test details

Test 1

Verdict: ACCEPTED

input
100000 100000
62 64 35 47 57 38 52 4 56 13 7...

correct output
831.753342
833.361649
833.847478
834.425131
831.468120
...

user output
831.753342
833.361649
833.847478
834.425131
831.468120
...