Code Submission Evaluation System Login

CSES - HIIT Open 2016

HIIT Open 2016

Contest start:2016-05-28 11:00:00
Contest end:2016-05-28 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2016-05-28 11:53:59
2016-05-28 11:09:00
Task:Approximate
Sender:LTR
Submission time:2016-05-28 11:53:59
Status:READY
Result:ACCEPTED

Show test data

Code

#include <iostream>
#include <vector>
#include <cstdio>

int main()
{
	int n, q;
	std::cin >> n >> q;
	std::vector<int> c;
	c.reserve(n);
	for (int i = 0; i < n; ++i) {
		int x;
		std::cin >> x;
		c.push_back(x);
	}

	// ith is the sum of values before but not inc. i
	std::vector<double> cumsums(n + 1);
	std::vector<double> cumsumsq(n + 1);
	cumsums[0] = 0.0;
	cumsumsq[0] = 0.0;
	for (int i = 1; i <= n; ++i) {
		cumsums[i] = c[i-1] + cumsums[i-1];
		cumsumsq[i] = c[i-1] * c[i-1] + cumsumsq[i-1];
	}

	for (int i = 0; i < q; ++i) {
		int a, b;
		std::cin >> a >> b;
		a--;
		b--;

		double num = b - a + 1;
		double mean = (cumsums[b+1] - cumsums[a]) / num;
		double ms = (cumsumsq[b+1] - cumsumsq[a]) / num;
		double err = ms - mean*mean;

		printf("%.6f\n", err);
	}
}