#include<iostream>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
#include<cmath>
#include<vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<cstdio>
#include<bitset>
#include<chrono>
#include<random>
#include<ext/rope>
/* ordered_set
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
*/
#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, q, a[maxN];
int _max[maxN], _min[maxN];
int l[maxN], r[maxN];
void ReadInput()
{
cin >> n >> q;
for(int i=1; i<=n; i++) cin >> a[i];
a[0] = -oo;
a[n + 1] = oo;
}
bool chk1(int i, int val)
{
int j = lower_bound(_min + 1, _min + q + 1, val) - _min;
if(j == q + 1) return false;
return a[i - 1] + _max[j] <= a[i] - val;
}
bool chk2(int i, int val)
{
int j = lower_bound(_max + 1, _max + q + 1, val) - _max;
if(j == q + 1) return false;
return a[i + 1] - _min[j] >= a[i] + val;
}
void Solve()
{
ll s = 0;
for(int i=1; i<=q; i++)
{
int x;
cin >> x;
s += x;
_max[i] = max(s, _max[i - 1]);
_min[i] = max(-s, _min[i - 1]);
}
for(int i=1; i<=n; i++)
{
int low = 1, high = oo, mid;
while(low <= high) /// Find l
{
mid = (low + high) / 2;
if(chk1(i, mid)) low = mid + 1;
else high = mid - 1;
}
l[i] = high;
low = 1, high = oo, mid;
while(low <= high) /// Find r
{
mid = (low + high) / 2;
if(chk2(i, mid)) low = mid + 1;
else high = mid - 1;
}
r[i] = high;
}
for(int i=1; i<=n; i++) cout << r[i] + l[i] << " ";
}
int32_t main()
{
freopen("x.inp", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ReadInput();
Solve();
}
Compilation message
Main.cpp: In function 'void Solve()':
Main.cpp:80:32: warning: right operand of comma operator has no effect [-Wunused-value]
80 | low = 1, high = oo, mid;
| ^
Main.cpp: In function 'int32_t main()':
Main.cpp:93:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
93 | freopen("x.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
