Submission #1056255

#TimeUsernameProblemLanguageResultExecution timeMemory
1056255SalihSahinSnowball (JOI21_ho_t2)C++17
100 / 100
238 ms18516 KiB
#include<bits/stdc++.h> #define int long long #define pb push_back #define double long double using namespace std; const int mod = 1e9 + 7; const int N = 2e5 + 5; int32_t main(){ ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0); int n, q; cin>>n>>q; vector<int> a(n); for(int i = 0; i < n; i++){ cin>>a[i]; } vector<int> df(n-1); for(int i = 1; i < n; i++){ df[i-1] = a[i] - a[i-1]; } vector<int> mx(q+1, 0), mn(q+1, 0), vals(q+1); vector<int> que(q); int sum = 0; for(int i = 0; i < q; i++){ cin>>que[i]; sum += que[i]; mx[i+1] = max(mx[i], sum); mn[i+1] = min(mn[i], sum); vals[i+1] = mx[i+1] - mn[i+1]; } vector<int> ans(n); for(int i = 0; i < n-1; i++){ if(vals[q] <= df[i]){ ans[i] += mx[q]; ans[i+1] += (-mn[q]); continue; } int l = 0, r = q; while(l < r){ int m = (l + r)/2; if(vals[m] <= df[i]) l = m + 1; else r = m; } l--; // first index <= ans[i] += mx[l]; ans[i+1] += (-mn[l]); if(que[l] < 0){ ans[i+1] += (df[i] - vals[l]); } else{ ans[i] += (df[i] - vals[l]); } } ans[0] += (-mn[q]); ans[n-1] += mx[q]; for(int i = 0; i < n; i++){ cout<<ans[i]<<endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...