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 << " ";
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 36/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1888 KiB | |||
2 | Elfogadva | 0/0 | 14ms | 2936 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2360 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2584 KiB | |||
5 | Elfogadva | 2/2 | 4ms | 2960 KiB | |||
6 | Elfogadva | 2/2 | 4ms | 3000 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 3216 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 3172 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3168 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 3428 KiB | |||
11 | Elfogadva | 2/2 | 14ms | 3964 KiB | |||
12 | Elfogadva | 2/2 | 86ms | 6560 KiB | |||
13 | Elfogadva | 2/2 | 104ms | 5296 KiB | |||
14 | Elfogadva | 2/2 | 193ms | 6840 KiB | |||
15 | Elfogadva | 2/2 | 193ms | 6800 KiB | |||
16 | Elfogadva | 2/2 | 194ms | 6840 KiB | |||
17 | Elfogadva | 2/2 | 194ms | 6836 KiB | |||
18 | Elfogadva | 2/2 | 123ms | 6800 KiB | |||
19 | Elfogadva | 2/2 | 254ms | 7004 KiB | |||
20 | Elfogadva | 2/2 | 257ms | 7080 KiB | |||
21 | Időlimit túllépés | 0/2 | 885ms | 4984 KiB | |||
22 | Időlimit túllépés | 0/2 | 865ms | 5024 KiB |