Submission #936759

#TimeUsernameProblemLanguageResultExecution timeMemory
936759vjudge1Snowball (JOI21_ho_t2)C++17
100 / 100
116 ms25100 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 1e6 + 7; const ll INF = 1e18 + 7; const int logo = 20; const int off = 1 << logo; ll L[MAXN], R[MAXN], arr[MAXN]; ll neg[MAXN], poz[MAXN], w[MAXN]; void solve(){ int n, q; cin >> n >> q; for(int i=1; i<=n; i++) cin >> arr[i]; ll cd = 0; for(int i=1; i<=q; i++){ cin >> w[i]; cd += w[i]; neg[i] = min(neg[i - 1], cd); poz[i] = max(poz[i - 1], cd); } L[1] = arr[1] + neg[q]; R[n] = arr[n] + poz[q]; for(int i=1; i<n; i++){ int lo = 1, hi = q, ret = -1; ll delt = arr[i + 1] - arr[i]; while(lo <= hi){ int mid = (lo + hi) / 2; if(poz[mid] + abs<ll>(neg[mid]) >= delt) ret = mid, hi = mid - 1; else lo = mid + 1; } if(ret == -1){ R[i] = arr[i] + poz[q]; L[i + 1] = arr[i + 1] + neg[q]; }else{ R[i] = arr[i] + poz[ret - 1]; L[i + 1] = arr[i + 1] + neg[ret - 1]; if(w[ret] < 0) L[i + 1] = R[i]; else R[i] = L[i + 1]; } } for(int i=1; i<=n; i++) cout << R[i] - L[i] << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tt = 1; //cin >> tt; while(tt--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...