#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
ll mx[MAX_N], mn[MAX_N], sum[MAX_N], delta[MAX_N];
const ll inf = 1ll << 60;
int n, q;
ll X[MAX_N];
ll res[MAX_N];
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> q;
for (int i = 1;i <= n;++i)
cin >> X[i];
for (int i = 1;i <= q;++i)
cin >> delta[i];
{
ll diff = 0;
for (int i = 1;i <= q;++i) {
diff += delta[i];
mx[i] = max(mx[i-1], diff);
mn[i] = min(mn[i-1], diff);
sum[i] = mx[i] - mn[i];
}
}
DE(mn[q], mx[q]);
{
X[0] = X[1] - inf;
X[n+1] = X[n] + inf;
for (int i = 1;i <= n + 1;++i) {
ll dis = X[i] - X[i-1];
int l = 0, r = q, mid;
while (l < r) {
mid = l + r >> 1;
if (sum[mid + 1] > dis)
r = mid;
else l = mid + 1;
}
ll tol = mn[l], tor = mx[l], lft = dis - (tor - tol);
res[i-1] += abs(tor);
res[i] += abs(tol);
if (l == q) continue;
if (delta[l + 1] <= 0)
res[i] += lft;
else
res[i-1] += lft;
}
}
for (int i = 1;i <= n;++i)
cout << res[i] << '\n';
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
Main.cpp:48:2: note: in expansion of macro 'DE'
48 | DE(mn[q], mx[q]);
| ^~
Main.cpp:60:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | mid = l + r >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
492 KB |
Output is correct |
| 17 |
Correct |
1 ms |
492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
620 KB |
Output is correct |
| 2 |
Correct |
1 ms |
492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
492 KB |
Output is correct |
| 5 |
Correct |
1 ms |
492 KB |
Output is correct |
| 6 |
Correct |
1 ms |
492 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
2 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
492 KB |
Output is correct |
| 10 |
Correct |
1 ms |
492 KB |
Output is correct |
| 11 |
Correct |
1 ms |
492 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
2 ms |
492 KB |
Output is correct |
| 16 |
Correct |
1 ms |
492 KB |
Output is correct |
| 17 |
Correct |
1 ms |
492 KB |
Output is correct |
| 18 |
Correct |
1 ms |
364 KB |
Output is correct |
| 19 |
Correct |
1 ms |
492 KB |
Output is correct |
| 20 |
Correct |
31 ms |
6636 KB |
Output is correct |
| 21 |
Correct |
30 ms |
6636 KB |
Output is correct |
| 22 |
Correct |
32 ms |
6660 KB |
Output is correct |
| 23 |
Correct |
30 ms |
6636 KB |
Output is correct |
| 24 |
Correct |
36 ms |
7148 KB |
Output is correct |
| 25 |
Correct |
132 ms |
11372 KB |
Output is correct |
| 26 |
Correct |
131 ms |
11372 KB |
Output is correct |
| 27 |
Correct |
124 ms |
11244 KB |
Output is correct |
| 28 |
Correct |
143 ms |
11244 KB |
Output is correct |
| 29 |
Correct |
127 ms |
11116 KB |
Output is correct |
| 30 |
Correct |
107 ms |
10604 KB |
Output is correct |
| 31 |
Correct |
87 ms |
10220 KB |
Output is correct |
| 32 |
Correct |
79 ms |
10220 KB |
Output is correct |
| 33 |
Correct |
11 ms |
1516 KB |
Output is correct |
| 34 |
Correct |
122 ms |
11372 KB |
Output is correct |
| 35 |
Correct |
132 ms |
11244 KB |
Output is correct |
| 36 |
Correct |
165 ms |
11500 KB |
Output is correct |
| 37 |
Correct |
122 ms |
11116 KB |
Output is correct |
| 38 |
Correct |
131 ms |
11372 KB |
Output is correct |
| 39 |
Correct |
109 ms |
11116 KB |
Output is correct |
| 40 |
Correct |
102 ms |
11116 KB |
Output is correct |
| 41 |
Correct |
33 ms |
6636 KB |
Output is correct |
| 42 |
Correct |
78 ms |
10220 KB |
Output is correct |
| 43 |
Correct |
99 ms |
11372 KB |
Output is correct |
| 44 |
Correct |
33 ms |
6636 KB |
Output is correct |
| 45 |
Correct |
86 ms |
11116 KB |
Output is correct |
| 46 |
Correct |
104 ms |
11628 KB |
Output is correct |
| 47 |
Correct |
104 ms |
11500 KB |
Output is correct |
| 48 |
Correct |
103 ms |
11500 KB |
Output is correct |
