54152023-05-14 18:41:47kicsiboglarGladiátorok (40 pont)cpp11Időlimit túllépés 36/40885ms7080 KiB
#include <iostream>
#include <vector>
#define f first
#define plus second
#include <algorithm>
#include <cmath>
using namespace std;

using ll = long long;
using P = pair<ll, ll>;
ll n, m, q, j, i, a, b;
vector <P> gl;

ll bs(ll r, ll l, ll a)
{
    if (r == l)
    {
        if (gl[r].first <= a) return r;
        else return r - 1;
    }
    ll middle = (r + l) / 2;
    if (gl[middle].first == a) return middle;
    if (gl[middle].first > a) return bs(r, middle, a);
    else return bs(middle + 1, l, a);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> q;
    gl.resize(n+1);
    for (i = 1; i <= n; ++i)
    {
        cin >> gl[i].f >> gl[i].plus;

    }

    sort(gl.begin() + 1, gl.end(), [](const P& a, const P& b)
        {
            return a.f < b.f;
        });
    for (i = 1; i <= n; ++i)
    {
       // gl[i].first = max(gl[i].fisrt,gl[i - 1].first);
        gl[i].plus += gl[i - 1].plus;
    }
    for (i = 1; i <= q; ++i)
    {
        cin >> a;
        if (a < gl[1].f)
        {
            cout << "0 ";
            continue;
        }
        b = bs(1, n, a);
        a += gl[b].plus;
        j = b;
        while (b<n&&a >= gl[b + 1].f)
        {
            b = bs(b+1, n, a);
            a += (gl[b].plus-gl[j].plus);
            j = b;
        }
        cout << b << " ";
    }
}