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:40:12
2016-05-28 11:18:03
Task:Approximate
Sender:ContinuedLife
Submission time:2016-05-28 11:40:12
Status:READY
Result:ACCEPTED

Show test data

Code

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout.precision(6);

using namespace std;

int main(){ _
	int n, q;
	cin >> n >> q;
	vector<int> vi(n, 0); 
	vector<int> sum(n, 0);
	vector<long long> sum2(n, 0);

	for(int i = 0; i < n; ++i)	cin >> vi[i];
	sum[0] = vi[0];
	for(int i = 1; i < n; ++i)	sum[i] = sum[i-1] + vi[i];

	for(int i = 0; i < n; ++i)	vi[i] = vi[i] * vi[i];
	sum2[0] = vi[0];
	for(int i = 1; i < n; ++i)	sum2[i] = sum2[i-1] + vi[i];

//	for(int i = 0; i < n; ++i)	cout << sum2[i] << endl;	

	int a, b, diff;
	double mean, ans;
	for(int i = 0; i < q; ++i){
		cin >> a >> b;
		a -= 2; b -= 1;
		
		if(a < 0)	diff = sum[b];
		else diff = sum[b] - sum[a];
		mean = diff / (double)(b - a);

//		cout << "a = " << a  << endl;
//		cout << "b = " << b << endl;
		// s_i^2 - 2s_ic_i + c_i^2
		if(a < 0)	ans = sum2[b];
		else ans = sum2[b] - sum2[a];
//		cout << "first = " << ans << endl;

		ans = ans - 2*diff*mean + (b-a)*mean*mean;


		ans /= (b-a);
		cout << fixed << ans << endl;
	}
	
	return 0;
}