/*
燒雞
燒雞
燒雞 好想進選訓
燒雞
燒雞
*/
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct node{
ll sum;
ll l;
ll r;
ll pl;
ll pr;
ll rans;
ll lans;
};
bool comp(node a,node b){
return a.sum<b.sum;
}
int main() {_
//setIO("wayne");
ll n,q;
cin>>n>>q;
ll num[n];
ll gapl[n],gapr[n];
for(ll i=0;i<n;i++){
cin>>num[i];
}
for(ll i=0;i<n-1;i++){
gapl[i]=num[i+1]-num[i];
gapr[i+1]=num[i+1]-num[i];
}
node cur;
cur.sum=cur.l=cur.r=cur.pr=cur.pl=cur.rans=cur.lans=0;
vector<node> left,right;
left.push_back(cur);
right.push_back(cur);
ll pos=0;
for(ll i=0;i<q;i++){
ll x;
cin>>x;
pos+=x;
if(x>=0){
cur.r=max(cur.r,pos);
cur.sum=cur.l+cur.r;
left.push_back(cur);
cur.pr=max(cur.pr,cur.r);
}
else{
cur.l=max(cur.l,-1*pos);
cur.sum=cur.l+cur.r;
right.push_back(cur);
cur.pl=max(cur.pl,cur.l);
}
}
sort(all(left),comp);
sort(all(right),comp);
vector<ll> lsum(left.size(),0);
vector<ll> rsum(right.size(),0);
vector<ll> lsum2(left.size(),0);
vector<ll> rsum2(right.size(),0);
vector<ll> lsum3(left.size(),0);
vector<ll> rsum3(right.size(),0);
for(ll i=1;i<left.size();i++){
lsum[i]=left[i].sum;
left[i].rans=left[i-1].rans+max(0ll,left[i].r-left[i].pr);
lsum2[i]=lsum3[i]=left[i].l+left[i].pr;
lsum2[i]+=lsum2[i-1];
left[i].l+=left[i-1].l;
left[i].r+=left[i-1].r;
left[i].pl+=left[i-1].pl;
left[i].pr+=left[i-1].pr;
}
for(ll i=1;i<right.size();i++){
rsum[i]=right[i].sum;
right[i].lans=right[i-1].lans+max(0ll,right[i].l-right[i].pl);
rsum2[i]=rsum3[i]=right[i].r+right[i].pl;
rsum2[i]+=rsum2[i-1];
right[i].l+=right[i-1].l;
right[i].r+=right[i-1].r;
right[i].pl+=right[i-1].pl;
right[i].pr+=right[i-1].pr;
}
vector<ll> ans(n,0);
for(ll i=0;i<n-1;i++){
ll gap=gapl[i];
ll pos=upper_bound(all(lsum),gap)-lsum.begin()-1;
ll pos2=upper_bound(lsum3.begin()+pos+1,lsum3.end(),gap)-lsum3.begin()-1;
ans[i]+=left[pos].rans;
ll sz=lsum.size();
ans[i]+=gap*(pos2-pos)-lsum2[pos2]+lsum2[pos];
//cout<<ans[i]<<' ';
}
//cout<<'\n';
//cout<<" ";
for(ll i=1;i<n;i++){
ll gap=gapr[i];
ll pos=upper_bound(all(rsum),gap)-rsum.begin()-1;
ll pos2=upper_bound(rsum3.begin()+pos+1,rsum3.end(),gap)-rsum3.begin()-1;
ans[i]+=right[pos].lans;
ll sz=rsum.size();
ans[i]+=gap*(pos2-pos)-rsum2[pos2]+rsum2[pos];
//cout<<right[pos].lans+gap*(pos2-pos)-rsum2[pos2]+rsum2[pos]<<' ';
}
ans[0]+=cur.l;
ans[n-1]+=cur.r;
//cout<<'\n';
for(ll i=0;i<n;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
//maybe its multiset not set
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:81:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
81 | for(ll i=1;i<left.size();i++){
| ~^~~~~~~~~~~~
Main.cpp:91:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for(ll i=1;i<right.size();i++){
| ~^~~~~~~~~~~~~
Main.cpp:107:12: warning: unused variable 'sz' [-Wunused-variable]
107 | ll sz=lsum.size();
| ^~
Main.cpp:118:12: warning: unused variable 'sz' [-Wunused-variable]
118 | ll sz=rsum.size();
| ^~
Main.cpp: In function 'void setIO(std::string)':
Main.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
20 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
584 KB |
Output is correct |
| 5 |
Correct |
2 ms |
584 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
2 ms |
584 KB |
Output is correct |
| 5 |
Correct |
2 ms |
584 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
540 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
