Ps_algorithm/10816bj.cpp at main · chanik-s/Ps_algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> a;
int n, m;
//int a[500005];
//int cnt[500005];

int lower_idx(int t,int len) {
	int st = 0, en = len;

	while (st < en) {

		int mid = (st + en) / 2;
		if (a[mid] >= t) {
			en = mid;
		}
		else {
			st = mid + 1;
		}
	}
	return st;
}
int upper_idx(int t, int len) {
	int st = 0, en = len;

	while (st < en) {

		int mid = (st + en) / 2;


		if (a[mid] > t) {
			en = mid;
		}
		else { //a[mid]==target
			st = mid + 1;
		}
	}
	return st;
}

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		int t;
		cin >> t;
		a.push_back(t);
	}
	sort(a.begin(), a.end());
	cin >> m;

	for (int i = 0; i < m; i++) {
		int t;
		cin >> t; //target ex>10
		cout << upper_idx(t, n)-lower_idx(t,n)<<' ';

	}
	/*
	vector<int> cnt(m);

	for (int i = 0; i < m; i++) {

		int t;
		cin >> t; //ºñ±³ÇÒ ¼ýÀÚ

		vector<int>::iterator low, up;
		low = lower_bound(a.begin(), a.end(), t);
		up = upper_bound(a.begin(), a.end(), t);

		int count = ((up - a.begin()) - (low - a.begin()));
		cnt[i] = count;
	}

	for (auto &i : cnt) {
		cout << i << ' ';
	}
	*/
	return 0;
}