#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tt;
#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())
const int mn = 2e5 + 5;
ll x[mn], pre[mn], ansLeft[mn], ansRight[mn];
void solve (vector<pl> &query, vector<pl> &vec, vector<int> &ans) {
int it = -1, curAns = INT_MAX;
for (auto [ub, iQry] : query) {
while (it + 1 < vec.size() && vec[it + 1].first <= ub)
curAns = min(curAns, (int)vec[++it].second);
ans[iQry] = curAns;
}
}
/*
main idea: binary search, for every snowball,
find the nearest position to its right
such that this snowball reaches that point
before the snowball right next to it.
at first glance, time complexity is O(2e5 log 1e12 log 2e5)
batch process all snowballs for O(2e5 log 1e12) time complexity
*/
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> x[i];
vector<pl> lVec, rVec;
lVec.push_back({0, 0});
rVec.push_back({0, 0});
for (int i = 1; i <= q; i++) {
ll w; cin >> w;
pre[i] = pre[i - 1] + w;
lVec.push_back({pre[i], i});
rVec.push_back({-pre[i], i});
}
sort(all(lVec)); sort(all(rVec));
/// process left side
for (ll mask = (1LL << 57); mask; mask >>= 1) {
vector<pl> lQuery, rQuery;
vector<int> lAns(n + 1), rAns(n + 1);
for (int i = 1; i <= n; i++) {
ll tmp = ansLeft[i] | mask;
// find the soonest wind for it to reach somewhere <= x[i] - tmp
lQuery.push_back({-tmp, i});
if (i > 1) {
// find the soonest wind for it to reach somewhere >= x[i] - tmp + 1
ll dest = x[i] - tmp + 1;
rQuery.push_back({-(dest - x[i - 1]), i - 1});
}
}
sort(all(lQuery)); sort(all(rQuery));
solve(lQuery, lVec, lAns);
solve(rQuery, rVec, rAns);
for (int i = 1; i <= n; i++) {
if (i == 1) {
if (lAns[i] != INT_MAX) ansLeft[i] |= mask;
}
else {
if (lAns[i] < rAns[i - 1]) ansLeft[i] |= mask;
}
}
}
/// process right side
for (ll mask = (1LL << 57); mask; mask >>= 1) {
vector<pl> lQuery, rQuery;
vector<int> lAns(n + 1), rAns(n + 1);
for (int i = 1; i <= n; i++) {
ll tmp = ansRight[i] | mask;
// find the soonest wind for it to reach somewhere >= x[i] + tmp
rQuery.push_back({-tmp, i});
if (i < n) {
// find the soonest wind for it to reach somewhere <= x[i] + tmp - 1
ll dest = x[i] + tmp - 1;
lQuery.push_back({dest - x[i + 1], i + 1});
}
}
sort(all(lQuery)); sort(all(rQuery));
solve(lQuery, lVec, lAns);
solve(rQuery, rVec, rAns);
for (int i = 1; i <= n; i++) {
if (i == n) {
if (rAns[i] != INT_MAX) ansRight[i] |= mask;
}
else {
if (rAns[i] < lAns[i + 1]) ansRight[i] |= mask;
}
}
}
for (int i = 1; i <= n; i++) {
//cout << ansLeft[i] << " " << ansRight[i] << " ";
cout << ansRight[i] + ansLeft[i] << "\n";
}
return 0;
}
Compilation message
Main.cpp: In function 'void solve(std::vector<std::pair<long long int, long long int> >&, std::vector<std::pair<long long int, long long int> >&, std::vector<int>&)':
Main.cpp:18:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
18 | for (auto [ub, iQry] : query) {
| ^
Main.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | while (it + 1 < vec.size() && vec[it + 1].first <= ub)
| ~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
604 KB |
Output is correct |
| 4 |
Correct |
29 ms |
776 KB |
Output is correct |
| 5 |
Correct |
25 ms |
600 KB |
Output is correct |
| 6 |
Correct |
26 ms |
604 KB |
Output is correct |
| 7 |
Correct |
23 ms |
604 KB |
Output is correct |
| 8 |
Correct |
23 ms |
604 KB |
Output is correct |
| 9 |
Correct |
26 ms |
756 KB |
Output is correct |
| 10 |
Correct |
24 ms |
856 KB |
Output is correct |
| 11 |
Correct |
14 ms |
604 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
3 ms |
348 KB |
Output is correct |
| 15 |
Correct |
27 ms |
772 KB |
Output is correct |
| 16 |
Correct |
28 ms |
604 KB |
Output is correct |
| 17 |
Correct |
29 ms |
600 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
22 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
600 KB |
Output is correct |
| 2 |
Correct |
1 ms |
612 KB |
Output is correct |
| 3 |
Correct |
3 ms |
604 KB |
Output is correct |
| 4 |
Correct |
29 ms |
776 KB |
Output is correct |
| 5 |
Correct |
25 ms |
600 KB |
Output is correct |
| 6 |
Correct |
26 ms |
604 KB |
Output is correct |
| 7 |
Correct |
23 ms |
604 KB |
Output is correct |
| 8 |
Correct |
23 ms |
604 KB |
Output is correct |
| 9 |
Correct |
26 ms |
756 KB |
Output is correct |
| 10 |
Correct |
24 ms |
856 KB |
Output is correct |
| 11 |
Correct |
14 ms |
604 KB |
Output is correct |
| 12 |
Correct |
1 ms |
348 KB |
Output is correct |
| 13 |
Correct |
1 ms |
348 KB |
Output is correct |
| 14 |
Correct |
3 ms |
348 KB |
Output is correct |
| 15 |
Correct |
27 ms |
772 KB |
Output is correct |
| 16 |
Correct |
28 ms |
604 KB |
Output is correct |
| 17 |
Correct |
29 ms |
600 KB |
Output is correct |
| 18 |
Correct |
1 ms |
344 KB |
Output is correct |
| 19 |
Correct |
22 ms |
604 KB |
Output is correct |
| 20 |
Correct |
63 ms |
12472 KB |
Output is correct |
| 21 |
Correct |
65 ms |
11452 KB |
Output is correct |
| 22 |
Correct |
74 ms |
12212 KB |
Output is correct |
| 23 |
Correct |
86 ms |
10440 KB |
Output is correct |
| 24 |
Correct |
384 ms |
12744 KB |
Output is correct |
| 25 |
Execution timed out |
2517 ms |
31368 KB |
Time limit exceeded |
| 26 |
Halted |
0 ms |
0 KB |
- |
