[C++] Prefix sum & static_cast / codeforces-276-C

https://codeforces.com/contest/276/problem/C

Problem - C - Codeforces

#include <bits/stdc++.h>

using namespace std;

int n, q;
int A[200005], R[200005] = {0};


int main()
{
	int i;
	int x, y;
	cin >> n >> q;

	for (i = 0; i < n; i++) {
		cin >> A[i];
	}

	// * 반복문 시간 & 메모리 줄이기
	// [시작 index -1] ++ , [마지막 index] -- 후 처음부터 더해줌.
	
	for (i = 0; i < q; i++) {
		cin >> x >> y;
		R[x - 1] += 1;
		R[y] -= 1;
	}

	for (i = 1; i < n; i++) {
		R[i] += R[i - 1];
	}

	// sort 후 반환 array는 작은 ~> 큰
	sort(A, A + n);
	sort(R, R + n);

	long long ans = 0;
	for (i = 0; i < n; i++) {
		//signed integer overflow가 발생하기 때문에 static_cast는 필수적이다.
		ans += static_cast<long long>(A[i]) * static_cast<long long>(R[i]);
		// ans += A[i] * R[i];
	}

	cout << ans << endl;

	return 0;
}