1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| #include <bits/stdc++.h>
#define R register
#define ll long long
#define pair std::pair<ll, ll>
#define mp(i, j) std::make_pair(i, j)
#define sum(a, b, mod) (((a) + (b)) % mod)
#define meow(cat...) fprintf(stderr, cat)
const ll MaxN = 2e5 + 10;
pair q[MaxN];
std::map<ll, ll> mp;
std::vector<pair> v;
ll n, m, now, a[MaxN], s[MaxN], ans[MaxN];
void init()
{
v.clear(), mp.clear(), now = 0;
for(ll i = 0; i < m + 10; i++)
ans[i] = -1;
for(ll i = 0; i < n + 10; i++)
a[i] = s[i] = 0;
}
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while(ch > '9' || ch < '0')
{
if(ch == '-')
f = 0;
ch = getchar();
}
while(ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? x : (-x);
}
signed main()
{
ll T = read();
while(T--)
{
n = read(), m = read(), init();
for(ll i = 1; i <= n; i++)
{
a[i] = read(), s[i] = a[i] + s[i - 1];
if(s[i] > 0 && !mp[s[i]])
mp[s[i]] = i, v.push_back(mp(s[i], i));
}
for(ll i = 1; i <= m; i++)
q[i].first = read(), q[i].second = i;
std::sort(q + 1, q + m + 1), std::sort(v.begin(), v.end());
if(v.size() >= 2)
{
for(ll i = v.size() - 2; i >= 0; i--)
{
ll x = mp[v[i].first];
x = std::min(x, mp.upper_bound(v[i].first)->second);
mp[v[i].first] = x, v[i].second = x;
}
}
for(ll i = 0; i < v.size(); i++)
{
while(now < m && q[now + 1].first <= v[i].first)
++now, ans[q[now].second] = v[i].second - 1;
}
for(ll i = now + 1; i <= m; i++)
{
if(s[n] <= 0) continue;
ans[q[i].second] = n * ((q[i].first - v.back().first + s[n] - 1) / s[n]);
q[i].first -= s[n] *((q[i].first - v.back().first + s[n] - 1) / s[n]),
ans[q[i].second] += mp.lower_bound(q[i].first)->second - 1;
}
for(ll i = 1; i <= m; i++)
printf("%lld%c", ans[i], " \n"[i == m]);
}
return 0;
}
|