백준 문제풀이

BOJ 3020.cpp

#include <bits/stdc++.h>
using namespace std;
const int MAX = 543211;
int N, H, Lo, Hi, tree[MAX+1];

int Li(int x){                
	return x&(-x);			 
}							
int sum(int i){
	int ans = 0;
	while(i>0){
		ans += tree[i];
		i -= Li(i);
	}
	return ans;
}
void update(int i, int diff){
	while(i<=H+1){
		tree[i] += diff;
		i += Li(i);
	}
}
int main(){ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);
cin >> N >> H;
// tree[1]: 1번째 구간(=0.5), tree[2]: 2번째 구간(=1.5), ...
for (int i = 0; i < N/2; ++i){
	cin >> Lo >> Hi;
	//석순
	update(H-Lo+1,1);
	update(H+1,-1);
	// 종유석
	update(1,1);
	update(Hi+1,-1);
}
int Whole = MAX;
int cnt = 0;
for (int i = 1; i <= H; ++i){
	int S = sum(i);
	if(S<Whole){
		Whole = S;
		cnt = 1;
	}
	else if(S==Whole) cnt++;
}

cout << Whole << ' ' << cnt << '\n';

return 0;
}