// ==========================================
// 1번 문제
// lower_bound / upper_bound 기초
// ==========================================

/*
반드시 데이터가 오름차순 정렬되어 있어야 쓸 수 있다. (이진 탐색 기반)
내가 지정한 값보다 '처음으로 큰(초과하는)' 값의 위치
인덱스를 구하고 싶다면 구해온 결과에서 - v.begin()



인덱스:   [0]   [1]   [2]   [3]   [4]   [5]   [6]
데이터:   10    20    30    30    30    40    50
int a = 10 ;  auto a= 10
auto it = upper_bound(v.begin(), v.end(), x);
auto it = upper_bound(v.begin(), v.end(), x);
int index = it - v.begin();  



오름차순으로 정렬된 수열이 주어진다.

각 질문마다:
L 이상 R 이하인 숫자의 개수를 출력하여라.

[입력]

[출력]

3
2
0

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {

    int N;
    cin >> N;

    vector<int> v(N);[0,0,0,0,0]

    for (int i = 0; i < N; i++) {
        cin >> v[i];
    }

// 5
// 1 4 6 8 10
// 3
// 1 6  ->L  R 1 4 6
// 5 9   ->
// 2 2

    int Q;
    cin >> Q;

    while (Q--) {  q=3

        int L, R;  1 6 
        cin >> L >> R;  v= [1,4,6,8,10]

        auto left = lower_bound(v.begin(), v.end(), L); 0

        auto right = upper_bound(v.begin(), v.end(), R);  2

        cout << right - left << '\n'; 2
    }
}




[힌트]

upper_bound - lower_bound 사용

*/


// ==========================================
// 2번 문제
// 거리 K 이하 학생 수 구하기
// ==========================================

/*

[문제]

학생 N명의 집 좌표가 주어진다.

각 학생마다:
거리 차이가 K 이하인 학생 수를 출력하여라.

자기 자신은 제외한다.

[입력]

5 3
1 4 6 8 12

[출력]

1 2 2 1 0

[힌트]

현재 학생 x라면:

x-K 이상
x+K 이하

범위를 이분탐색으로 찾기

*/


// ==========================================
// 3번 문제
// 구조체 + 정렬 + 학교별 저장
// ==========================================

/*

[문제]

학생들의 좌표와 학교 번호가 주어진다.

각 학교별 학생 좌표를 오름차순 출력하여라.

[입력]

6
10 2
3 1
15 2
7 1
20 3
5 1

[출력]

school 1 : 3 5 7
school 2 : 10 15
school 3 : 20

[힌트]

vector<vector<int>>
사용

*/


// ==========================================
// 4번 문제
// KOI 축소판 (최종 연습)
// ==========================================

/*

[문제]

학생들의 집 좌표와 학교 번호가 주어진다.

- 같은 학교:
거리 <= K1

- 다른 학교:
거리 <= K2

일 때 각 학생의 친구 수를 출력하여라.

[입력]

5 5 2
1 1
3 2
6 1
8 2
10 1

[출력]

2 1 3 2 2

[힌트]

1.
전체 학생 기준 K2 친구 수 계산

2.
같은 학교 학생들 중
K2 기준 제거

3.
같은 학교 학생들 중
K1 기준 추가

4.
lower_bound / upper_bound 사용

*/