#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
using namespace std;
#define debug(args...) cout << '[' << #args << "] is [", DEBUG(false, args), cout << ']' << endl
template<typename T>
void DEBUG(bool _sp, T i) {
if (_sp)
cout << ' ';
cout << i;
}
template<typename T, typename ...U>
void DEBUG(bool _sp, T i, U ...j) {
if (_sp)
cout << ' ';
cout << i;
DEBUG(true, j...);
}
template<typename T, typename U>
ostream& operator << (ostream &i, pair<T, U> j) {
i << '(' << j.first << ", " << j.second << ')';
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
i << '{' << j.size() << " :";
for (T _i : j)
i << ' ' << _i;
i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
typedef double dd;
const int inf = 0x3f3f3f3f, lg = 20;
const ll mod = 1e9 + 7, INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<ll, int> pl;
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
int n, q;
cin >> n >> q;
ll a[n], b[q];
for (ll &i : a)
cin >> i;
for (ll &i : b)
cin >> i;
for (int i = 1; i < q; ++i)
b[i] += b[i - 1];
vector<pl> vl, vr;
for (int i = 0; i < q; ++i) {
if (b[i] < 0)
vl.emplace_back(-b[i], i);
else if (b[i] > 0)
vr.emplace_back(b[i], i);
}
sort(all(vl)), sort(all(vr));
vector<pl> tmp;
for (auto [i, j] : vl) {
while (!tmp.empty() && tmp.back().second >= j)
tmp.pop_back();
tmp.emplace_back(i, j);
}
vl = tmp, tmp.clear();
for (auto [i, j] : vr) {
while (!tmp.empty() && tmp.back().second >= j)
tmp.pop_back();
if (tmp.empty() || tmp.back().first < i)
tmp.emplace_back(i, j);
}
vr = tmp;
ll ans[n]{}, mxl = vl.back().first, mxr = vr.back().first;
ans[0] += mxl, ans[n - 1] += mxr;
for (int i = 0; i < n - 1; ++i) {
if (a[i + 1] - a[i] >= mxl + mxr) {
ans[i] += mxr, ans[i + 1] += mxl;
continue;
}
ll len = a[i + 1] - a[i];
ll l = max(0ll, len - mxl), r = min(len, mxr) + 1;
while (l < r - 1) {
ll mid = l + r >> 1;
if (lower_bound(all(vr), pl(mid, -1))->second < lower_bound(all(vl), pl(len - mid + 1, -1))->second)
l = mid;
else
r = mid;
}
ans[i] += l, ans[i + 1] += len - l;
}
for (ll i : ans)
cout << i << '\n';
}
Compilation message
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::pair<_T1, _T2>)':
Main.cpp:21:1: warning: no return statement in function returning non-void [-Wreturn-type]
21 | }
| ^
Main.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<_Tp>)':
Main.cpp:28:1: warning: no return statement in function returning non-void [-Wreturn-type]
28 | }
| ^
Main.cpp: In function 'int main()':
Main.cpp:82:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
82 | ll mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
5 ms |
460 KB |
Output is correct |
| 5 |
Correct |
4 ms |
460 KB |
Output is correct |
| 6 |
Correct |
4 ms |
372 KB |
Output is correct |
| 7 |
Correct |
4 ms |
428 KB |
Output is correct |
| 8 |
Correct |
4 ms |
464 KB |
Output is correct |
| 9 |
Correct |
3 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| 2 |
Correct |
1 ms |
324 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| 4 |
Correct |
5 ms |
460 KB |
Output is correct |
| 5 |
Correct |
4 ms |
460 KB |
Output is correct |
| 6 |
Correct |
4 ms |
372 KB |
Output is correct |
| 7 |
Correct |
4 ms |
428 KB |
Output is correct |
| 8 |
Correct |
4 ms |
464 KB |
Output is correct |
| 9 |
Correct |
3 ms |
460 KB |
Output is correct |
| 10 |
Correct |
2 ms |
460 KB |
Output is correct |
| 11 |
Runtime error |
1 ms |
588 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
