[구간합] 개똥벌레_백준 구간합 풀이법

#include <iostream>
#include <vector>
using namespace std;

int N, M;
const int MAX_N = 200000 + 1;

vector<int> BottomUp(100000);
vector<int> TopDown(100000);

vector<int> ARR_BottomUp(500000, 0);
vector<int> ARR_TopDown(500000, 0);

vector<int> SUM_BottomUp(500000 + 1);
vector<int> SUM_TopDown(500000 + 1);

pair<int, int> solution() {
	pair<int, int> answer = {MAX_N, 0};

	// 구간합을 구하기 위한 ARR 배열 만들기
	for (int i = 0; i < N / 2; i++) {
		ARR_BottomUp[BottomUp[i]]++;
		ARR_TopDown[TopDown[i]]++;
	}
	
	for (int i = 0; i <= M; i++) {
		SUM_BottomUp[i + 1] = SUM_BottomUp[i] + ARR_BottomUp[i];
		SUM_TopDown[i + 1] = SUM_TopDown[i] + ARR_TopDown[i];
	}

	for (int h = 0; h <= M; h++) {
		int cnt = 0;

		cnt += SUM_BottomUp[M+1] - SUM_BottomUp[h + 1];

		int reverseH = M - h;
		if (reverseH == 0)
			break;
		cnt += SUM_TopDown[M+1] - SUM_TopDown[reverseH];
		
		if (answer.first > cnt) {
			answer.first = cnt;
			answer.second = 1;
		}
		else if(answer.first == cnt){
			answer.second++;
		}
	}

	return answer;
}

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		if (i % 2 == 0)
			cin >> BottomUp[i / 2];	
		else
			cin >> TopDown[i / 2];
	}

	pair<int, int> answer = solution();
	cout << answer.first << " " << answer.second << endl;

	return 0;
}