This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define db double
#define ll __int128
#define int long long
#define pb push_back
#define fs first
#define sd second
#define Mod long(1e9 + 7)
#define all(x) x.begin(), x.end()
#define unvisited long(-1)
#define Eps double(1e-9)
#define _for(i, n) for(int i = 0; i < (n); i++)
#define dbg(x) cout << #x ": " << x << endl;
const int Max = 1e6 + 7, Inf = 1e18 + 7;
void print(bool x) { cout << (x ? "YES" : "NO") << endl; }
string tostring (__int128 x)
{
string ans = "";
while(x > 0)
{
ans += (x % 10 + '0');
x /= 10;
}
reverse(all(ans));
return ans;
}
void solve()
{
int n, q; cin >> n >> q;
vector <int> v(n);
for(auto& u : v) cin >> u;
vector <int> s(q), mx(q), mn(q);
for(int i = 0; i < q; i++)
{
cin >> s[i];
if(i != 0)
{
s[i] += s[i-1];
mn[i] = min(s[i], mn[i-1]);
mx[i] = max(s[i], mx[i-1]);
}
else
{
mn[i] = mx[i] = s[i];
}
}
for(int i = 0; i < n; i++)
{
int a = -1, b = q, ans = 0, x, y;
x = v[i]; y = (i+1 != n ? v[i+1] : Inf);
while(abs(a - b) != 1)
{
int c = (a + b) / 2;
if(mx[c] + x < mn[c] + y)
a = c;
else
b = c;
}
if(a != -1)
{
int temp = 0, t = a;
for(int j = 0; j + t < q && j < 5; j++)
{
temp = max(temp, min(min((y + mn[a]), (x + mx[a])) - x, abs(x - y)));
//cerr << min((y + mn[a]), (x + mx[a])) - x << " " << min((y + mn[a]), (x + mx[a])) << " "<< temp << endl;
a++;
}
ans += temp; //cerr << "A: " << mx[a] << " " << temp << endl;
}
a = -1; b = q;
x = v[i]; y = (i != 0 ? v[i-1] : -Inf);
while(abs(a - b) != 1)
{
int c = (a + b) / 2;//cerr << mx[c] + x << " " << mn[c] + y << endl;
if(mn[c] + x > mx[c] + y)
a = c;
else
b = c;
} //cerr << a << " " << mn[a] << endl;
if(a != -1)
{
int temp = 0, t = a; //cerr << a << " " << x - mn[a] << " " << mx[a] << endl;
for(int j = 0; j + t < q && j < 5; j++)
{ //cerr << max((x + mn[a]), (y + mx[a])) << endl;
temp = max(temp, min(x - max((x + mn[a]), (y + mx[a])), abs(x - y)));
a++;
}
ans += temp; //cerr << "B: " << mx[a] << " " << temp << endl;
}
cout << ans << endl;
}
}
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int Q = 1; //cin >> Q;
while (Q--)
{
solve();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |