This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optmize ("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define spIO ios::sync_with_stdio(false);cin.tie(0)
#define mem(x,va) memset(x,va,sizeof(x))
#define for0(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
typedef long long ll;
typedef long double ld;
const ll mod = 1e9 + 7;
inline ll inv(ll x, ll MOD = mod)
{
ll power = MOD - 2, ret = 1;
while (power)
{
if (power & 1)
(ret *= x) %= MOD;
power >>= 1;
(x *= x) %= MOD;
}
return ret;
}
inline ll gcd(ll x, ll y)
{
if (y == 0) return x;
return gcd(y, x % y);
}
ll pow2(ll target, ll p)
{
ll ret = 1;
while (p)
{
if (p & 1)
(ret *= target) %= mod;
p >>= 1;
(target *= target) %= mod;
}
return ret;
}
ll n, q;
ll x[200000 + 5], w[200000 + 5], r[200000 + 5], l[200000 + 5], ans[200000 + 5];
ll bs(ll tar)
{
int left = 0, right = q + 1, mid;
while (left != right)
{
mid = (left + right) / 2;
if (r[mid] + l[mid] <= tar)
left = mid + 1;
else
right = mid;
}
return left;
}
int main()
{
spIO;
cin >> n >> q;
for1(i, n) cin >> x[i];
for1(i, q) cin >> w[i];
ll ip = 0;
l[0] = r[0] = 0;
for1(i, q)
{
ip += w[i];
r[i] = max(r[i - 1], ip);
l[i] = max(l[i - 1], -ip);
}
ans[1] += l[q];
for (int i = 2; i <= n; i++)
{
if (l[q] + r[q] <= x[i] - x[i - 1])
{
ans[i - 1] += r[q];
ans[i] += l[q];
}
else
{
ll t = bs(x[i] - x[i - 1]);
if (r[t] - r[t - 1] > 0)
{
ans[i - 1] += x[i] - x[i - 1] - l[t];
ans[i] += l[t];
}
else
{
ans[i] += x[i] - x[i - 1] - r[t];
ans[i - 1] += r[t];
}
}
//cout << i - 1 << ' ' << i << ' ' << ans[i - 1] << ' ' << ans[i] << '\n';
}
ans[n] += r[q];
for1(i, n) cout << ans[i] << ' '; cout << '\n';
}
/*
*/
Compilation message (stderr)
Main.cpp:1: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
1 | #pragma GCC optmize ("O3,unroll-loops")
|
Main.cpp: In function 'int main()':
Main.cpp:7:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
7 | #define for1(i,n) for(int i=1;i<=n;i++)
| ^~~
Main.cpp:98:2: note: in expansion of macro 'for1'
98 | for1(i, n) cout << ans[i] << ' '; cout << '\n';
| ^~~~
Main.cpp:98:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
98 | for1(i, n) cout << ans[i] << ' '; cout << '\n';
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |