#include <iostream>
#include <iomanip>
#include <cassert>
#include <vector>
#include <numeric>
#include <string>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <random>
#include <ctime>
#include <chrono>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#ifdef __APPLE__
#include "debug.h"
//#define debug(...) 42
#else
#define debug(...) 42
#endif
//#define int ll
void solve() {
int n, q;
cin >> n >> q;
vector<ll> x(n + 2), qs(q);
for (int i = 1; i <= n; ++i) {
cin >> x[i];
}
x[0] = -INFLL;
x[n + 1] = INFLL;
ll go_left = 0, go_right = 0, d = 0;
vector<ll> jumps_left(1, 0), jumps_right(1, 0);
vector<int> id_left(1, -1), id_right(1, -1);
for (int i = 0; i < q; ++i) {
cin >> qs[i];
d += qs[i];
if (d < go_left) {
go_left = d;
jumps_left.emplace_back(abs(d));
id_left.emplace_back(i);
}
if (d > go_right) {
go_right = d;
jumps_right.emplace_back(d);
id_right.emplace_back(i);
}
}
vector<ll> l(n + 2), r(n + 2);
for (int i = 0; i < n + 2; ++i) {
l[i] = x[i] + go_left;
r[i] = x[i] + go_right;
}
vector<ll> ans(n + 2, 0);
ans[1] += abs(go_left);
ans[n] += go_right;
for (int i = 2; i <= n; ++i) {
if (r[i - 1] <= l[i] || (r[i - 1] == x[i - 1] && l[i] <= x[i - 1])) {
ans[i - 1] += go_right;
ans[i] += (x[i] - x[i - 1]);
}
else {
ll lx = l[i], rx = min(r[i - 1], x[i]) + 1;
ans[i - 1] += (lx - x[i - 1]);
while (rx - lx > 1) {
ll mx = lx + (rx - lx) / 2;
int id1 = (int)(lower_bound(all(jumps_right), mx - x[i - 1]) - jumps_right.begin());
int id2 = (int)(lower_bound(all(jumps_left), x[i] - mx + 1) - jumps_left.begin());
int ev1 = id_right[id1], ev2 = id_left[id2];
if (ev1 < ev2) {
lx = mx;
}
else {
rx = mx;
}
}
ans[i - 1] += (lx - l[i]);
ans[i] += (x[i] - lx);
}
}
for (int i = 1; i <= n; ++i) {
cout << ans[i] << en;
}
}
int32_t main() {
#ifdef __APPLE__
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
468 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
