//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define vi vector<int>
#define vl vector<ll>
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(false); cin.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
ll a[MAX], ans[MAX];
pll rng[MAX];
void solve(){
int n, q;
cin >> n >> q;
for(int i = 1;i <= n;i++){
cin >> a[i];
}
ll mx = 0, mn = 0, now = 0;
for(int i = 1;i <= q;i++){
ll x;
cin >> x;
now += x;
mx = max(mx, now);
mn = min(mn, now);
rng[i] = {mn, mx};
cout << i << " " << mn << " " << mx << '\n';
}
ans[1] = -rng[q].F;
ans[n] = rng[q].S;
for(int i = 1;i < n;i++){
ll l = 0, r = q + 1;
while(l < r){
int mid = (r - l) / 2 + l;
if(a[i] + rng[mid].S <= a[i + 1] + rng[mid].F)
l = mid + 1;
else
r = mid;
}
l--;
// cout << i << " " << l << '\n';
ans[i] += rng[l].S;
ans[i + 1] += -rng[l].F;
if(l == q)
continue;
if(rng[l + 1].S > rng[l].S)
ans[i] += (rng[l + 1].F + a[i + 1]) - (rng[l].S + a[i]);
else
ans[i + 1] += (a[i + 1] + rng[l].F) - (a[i] + rng[l].S);
}
for(int i = 1;i <= n;i++)
cout << ans[i] << '\n';
}
int main(){
IOS
// CASE
solve();
return 0;
}
/*
10 10
-56 -43 -39 -31 -22 -5 0 12 18 22
-3
0
5
-4
-2
10
-13
-1
9
6
1 -3 0
2 -3 0
3 -3 2
4 -3 2
5 -4 2
6 -4 6
7 -7 6
8 -8 6
9 -8 6
10 -8 7
1 7
2 2
3 5
4 5
5 9
6 4
7 6
8 5
9 2
14
8
7
9
13
10
9
8
5
10
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
