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 <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>
//using ll = int64_t;
#define pb push_back
#define all(a) a.begin(),a.end()
#define ppi pair<int,pair<int,int>>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int int64_t
// xcode cant include bits/stdc++.h
using namespace std;
/* /\_/\
* (= ._.)
* / > \>
*/
// encouraging cat
const int INF = 1000000;
const int mod = 1000000007;
const int MAXN = 2e5+5;
int n,q;
int pre1[MAXN + 1],pre2[MAXN + 1];
bool check(int k,int tmp)
{
return ((pre1[k]+pre2[k])<=tmp);
}
int32_t main()
{
cin >> n >> q;
vector<int> x(n + 1),a(n + 1),w(n + 1),sum(n + 1);
vector<pair<int,int>> b(n + 1);
for(int i = 1;i <= n;i++)
{
cin >> x[i];
}
for(int i = 1;i <= q;i++)
{
cin >> w[i];
}
sum[0] = 0;
pre1[0] = pre2[0] = 0;
for(int j = 1;j <= q;j++)
{
sum[j] = sum[j-1] + w[j];
pre1[j] = max(pre1[j - 1],sum[j]);
pre2[j] = max(pre2[j - 1],-sum[j]);
}
a[1] = pre2[q];
a[n] = pre1[q];
for(int i = 1;i < n;i++)
{
int tmp = x[i + 1] - x[i];
int l = 1,r = q,res=0;
while(l <= r)
{
int mid = (l + r) / 2;
if(check(mid,tmp))
{
res = mid;
l = mid+1;
}
else
r = mid-1;
}
if(res > 0)
{
b[i].first = pre1[res];
b[i].second = pre2[res];
}
if(res < q)
{
int pre_l = b[i].first,pre_r = b[i].second;
int cur = tmp - pre_l - pre_r;
if(sum[res + 1] > 0)
{
b[i].first += cur;
}
else
b[i].second+=cur;
}
}
for(int i = 1;i <= n;i++)
{
if(i<n)
{
a[i] += b[i].first;
a[i+1] += b[i].second;
}
cout <<a[i] <<'\n';
}
return 0;
}
Compilation message (stderr)
Main.cpp:31:9: warning: "/*" within comment [-Wcomment]
31 | /* /\_/\
|
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |