Cod sursa(job #3303015)

Utilizator InformaticianInDevenire1Munteanu Mihnea Gabriel InformaticianInDevenire1 Data 12 iulie 2025 17:33:12
Problema Deque Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#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;
}