5415 2023-05-14 18:41:47 kicsiboglar Gladiátorok (40 pont) cpp11 Időlimit túllépés 36/40 885ms 7080 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 << " ";
}
}