백준 17393 다이나믹 롤러

https://www.acmicpc.net/problem/17393

숭고한 공식 풀이는 여기서 보실 수 있습니다.

upper_bound 는 여기서 확인할 수 있습니다.

잉크지수보다 큰 수 중에 가장 작은 수의 인덱스를 upper_bound를 이용해 찾으면 멩미가 서있는 인덱스와 upper_bound 사이의 인덱스를 칠할 수 있게 됩니다.

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int SZ=500005;
ll arr[SZ];
vector<ll> v;
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>arr[i];
	for(int i=0;i<n;i++){
		ll x; cin>>x;
		v.pb(x);
	}
	for(int i=0;i<n;i++){
		int p=(int)(upper_bound(v.begin(),v.end(),arr[i])-v.begin());
		p=p<i+1?0:p-i-1;
		cout<<p<<" ";
	}
	return 0;
}