Queries about less or equal elements - Codeforces - 600B
You are given two arrays of integers a and b. For each element of the second array bj you should find the number of elements in array a that are less than or equal to the value bj.
Input
The first line contains two integers n, m (1 ≤ n, m ≤ 2·10^5) — the sizes of arrays a and b.
The second line contains n integers — the elements of array a ( - 10^9 ≤ ai ≤ 10^9).
The third line contains m integers — the elements of array b ( - 10^9 ≤ bj ≤ 10^9).
Output
Print m integers, separated by spaces: the j-th of which is equal to the number of such elements in array a that are less than or equal to the value bj.
Example
Input
5 4
1 3 5 7 9
6 4 2 8
Output
3 2 1 4
Input
5 5
1 2 1 2 5
3 1 4 1 5
Output
4 2 4 2 5
제목:
두 배열 에 게 두 번 째 배열 의 모든 요 소 를 첫 번 째 배열 에서 그것 과 같은 수의 개 수 를 찾 아 라.
생각:
폭력 은 안 될 것 이다. 두 배열 의 길 이 는 모두 105 의 수량 급 에 이 를 수 있 고 폭력 을 찾 는 데 적어도 100 초 는 걸린다.이 문 제 는 여러 가지 방법 이 있 습 니 다. 제 방안 은 배열 요 소 를 분 산 된 후에 나무 모양 배열 로 각 숫자의 출현 횟수 를 기록 한 다음 에 두 번 째 배열 로 구간 과 방식 을 조회 하여 답 을 푸 는 것 입 니 다.두 배열 의 요 소 를 합 쳐 이 집합 을 이산 화 처리 하 는 것 에 만 주의 하 세 요.첫 번 째 배열 을 정렬 한 후 upper 를 사용 하 는 더 쉬 운 STL 방법 도 있 습 니 다.bound () 함 수 는 두 번 째 배열 의 모든 요소 가 첫 번 째 배열 에서 어느 위치 에 있 는 지 확인 하면 답 을 편리 하 게 알 수 있 습 니 다.
#include
#include
#include
#include
using namespace std;
const int maxn = 2e5+19;
int n, m;
int C[maxn<<1];
int sample[maxn<<1];
int a[maxn], b[maxn];
void add(int x, int d){
while(x <= n+m){
C[x] += d; x += x&-x;
}
}
int sum(int x){
int ret = 0;
while(x){
ret += C[x]; x -= x&-x;
}
return ret;
}
int main()
{
#ifdef TEST
freopen("test.txt", "r", stdin);
#endif // TEST
while(cin >> n >> m){
memset(C, 0, sizeof(C));
for(int i = 0; i < n; i++){
scanf("%d", &a[i]);
sample[i] = a[i];
}
for(int i = 0; i < m; i++){
scanf("%d", &b[i]);
sample[n+i] = b[i];
}
sort(sample, sample+m+n);
int len = unique(sample, sample+m+n) - sample;
for(int i = 0; i < n; i++){
a[i] = lower_bound(sample, sample+len, a[i]) - sample + 1;
add(a[i], 1);
}
for(int i = 0; i < m; i++){
b[i] = lower_bound(sample, sample+len, b[i]) - sample + 1;
}
for(int i = 0; i < m; i++){
printf("%d%c", sum(b[i]), "
"[i==m-1]);
}
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
|NOIOJ|2분|04: 네트워크 관리자심판위원회는 인터넷 라인을 구매하기 위해 현지의 한 인터넷 솔루션 제공 업체에 연락하여 일정한 수량의 등장망 라인을 제공할 수 있도록 요구했다.심판위원회는 네트워크가 길어질수록 좋아져 선수들 사이의 거리가 가능한 한...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.