LISに近い問題. 実験してみると,子供 \(i \in N\) が食べた最大の寿司を \(v_{i}\) とおくと, \(v\) は常に降順. よって,誰が食べるのかは binary search で求まる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m;
cin >> n >> m;
vll a(m); rep(i,m) { cin >> a[i]; a[i] *= -1; }
vll v(n,INFL);
rep(i,m){
auto it = upper_bound(all(v), a[i]);
ll x;
if(it != v.end()){
*it = a[i];
x = it - v.begin();
}else{
x = -2;
}
cout << x+1 << endl;
}
return 0;
}