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>
#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>
using namespace std;
const int MAXN = 1e5+5;
const int mod7 = 1e9+7;
const long long inf = 1e18;
signed main()
{
ios_base::sync_with_stdio(false),cin.tie(0), cout.tie(0);
int tt=1;
//cin >> tt;
while(tt--)
{
int n,q;
cin >> n >> q;
vector<int> niz(n);
vector<int> maxdelta(q+1, 0);
vector<int> mindelta(q+1, 0);
vector<int> query(q);
for(int i=0; i<n; i++)cin >> niz[i];
int delta= 0;
for(int i= 0; i<q; i++)
{
cin >> query[i];
delta += query[i];
mindelta[i+1] = min(mindelta[i], delta);
maxdelta[i+1] = max(maxdelta[i], delta);
}
for(int i=1; i<=q; i++)mindelta[i]*=-1;
vector<int> deltaR(n, 0);
vector<int> deltaL(n, 0);
deltaR[n-1] = maxdelta[q];
deltaL[0] = mindelta[q];
maxdelta.pb(inf);
mindelta.pb(inf);
for(int i=0; i<n-1; i++)
{
int l = 0;int r = niz[i+1] - niz[i];
int rez = 0;
while(l<=r)
{
int mid = l+r>>1;
int index = lower_bound(all(maxdelta), mid) - maxdelta.begin();
if(niz[i] + mid <= niz[i+1] - mindelta[index])
{
l = mid+1;
rez = mid;
}
else r = mid-1;
}
deltaR[i] = rez;
}
for(int i=n-1; i>0; i--)
{
int l = 0;int r = niz[i] - niz[i-1];
int rez = 0;
while(l<=r)
{
int mid = l+r>>1;
int index = lower_bound(all(mindelta), mid) - mindelta.begin();
if(niz[i] - mid >= niz[i-1] + maxdelta[index])
{
l = mid+1;
rez = mid;
}
else r = mid-1;
}
deltaL[i] = rez;
}
for(int i=0; i<n; i++)cout << deltaL[i] + deltaR[i] << endl;
}
}
/*
1 4
1000000000000
1000000000000
-1000000000000
-1000000000000
-1000000000000
*/
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:52:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
52 | int mid = l+r>>1;
| ~^~
Main.cpp:69:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int mid = l+r>>1;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |