Pagini recente » Monitorul de evaluare | Cod sursa (job #3309654) | Autentificare | Cod sursa (job #3302643) | Cod sursa (job #3303015)
#include <bits/stdc++.h>
using namespace std;
vector <int> v(200005,0);
int bkt[1005]; // bucket, not backtracking
int B = 450;
int n,m;
int Find_Bucket(int x){
return x/B;
}
int Find_Pos(int x){
return x%B;
}
long long Query(int x){
for (int i=0;i<=Find_Bucket(n);++i){
if (bkt[i]<x) continue;
for (int j=0;j<B;++j){
int I = i*B+j;
if (I>n) break;
if (v[I]>=x) return I;
}
}
return 0;
}
void Update(int I,int x){
int b = Find_Bucket(I);
v[I] -= x;
bkt[b] = max(bkt[b],v[I]);
if (v[I]+x==bkt[b]){
bkt[b] = 0;
for (int i=b*B;i<min(n+1,(b+1)*B);++i){
bkt[b] = max(bkt[b], v[i]);
}
}
return;
}
signed main()
{
//freopen("input.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> m;
v[0] = -2;
for (int i=1;i<=n;++i){
cin >> v[i];
bkt[Find_Bucket(i)] = max(bkt[Find_Bucket(i)],v[i]);
}
for (int i=1;i<=m;++i){
int x;
cin >> x;
long long ans = Query(x);
cout << ans << ' ';
if (ans==0) continue;
Update(ans,x);
}
return 0;
}