5414 | 2023. 05. 14 18:40:02 | kicsiboglar | Gladiátorok (40 pont) | cpp11 | Időlimit túllépés 36/40 | 870ms | 7332 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 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 | 1764 KiB | |||
2 | Elfogadva | 0/0 | 13ms | 2748 KiB | |||
3 | Elfogadva | 2/2 | 3ms | 2172 KiB | |||
4 | Elfogadva | 2/2 | 3ms | 2252 KiB | |||
5 | Elfogadva | 2/2 | 4ms | 2544 KiB | |||
6 | Elfogadva | 2/2 | 4ms | 2756 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 2708 KiB | |||
8 | Elfogadva | 2/2 | 4ms | 2968 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 3180 KiB | |||
10 | Elfogadva | 2/2 | 4ms | 3140 KiB | |||
11 | Elfogadva | 2/2 | 13ms | 3520 KiB | |||
12 | Elfogadva | 2/2 | 82ms | 6064 KiB | |||
13 | Elfogadva | 2/2 | 96ms | 4484 KiB | |||
14 | Elfogadva | 2/2 | 184ms | 6264 KiB | |||
15 | Elfogadva | 2/2 | 184ms | 6560 KiB | |||
16 | Elfogadva | 2/2 | 185ms | 6772 KiB | |||
17 | Elfogadva | 2/2 | 182ms | 7088 KiB | |||
18 | Elfogadva | 2/2 | 118ms | 7092 KiB | |||
19 | Elfogadva | 2/2 | 243ms | 7120 KiB | |||
20 | Elfogadva | 2/2 | 245ms | 7332 KiB | |||
21 | Időlimit túllépés | 0/2 | 869ms | 5172 KiB | |||
22 | Időlimit túllépés | 0/2 | 870ms | 5160 KiB |