Submission #396917

#TimeUsernameProblemLanguageResultExecution timeMemory
396917AQTSnowball (JOI21_ho_t2)C++14
0 / 100
1 ms332 KiB
#include <bits/stdc++.h> using namespace std; int N, Q; long long x[200005]; long long w[200005]; long long d[200005]; long long lft[200005], rht[200005]; long long ans[200005]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N >> Q; for(int i = 1; i <= N; i++){ cin >> x[i]; } for(int i = 1; i <= Q; i++){ cin >> d[i]; d[i] += d[i-1]; } for(int i = 1; i <= Q; i++){ if(d[i] < 0){ rht[i] = -d[i]; } else{ lft[i] = d[i]; } rht[i] = max(rht[i], rht[i-1]); lft[i] = max(lft[i], lft[i-1]); } ans[1] = rht[Q]; ans[N] += lft[Q]; for(int i = 1; i < N; i++){ if(lft[Q] + rht[Q] > x[i + 1] - x[i]){ int l = 1, r = N, k = 0; while(l <= r){ int mid = (l + r)/2; if(lft[mid] + rht[mid] < x[i + 1] - x[i]){ l = mid + 1; } else{ r = mid - 1; k = mid; } } ans[i] += lft[k-1]; ans[i+1] += rht[k-1]; if(lft[k-1] != lft[k]){ ans[i] += x[i + 1] - x[i] - lft[k-1] - rht[k-1]; } else{ ans[i+1] += x[i+1] - x[i] - lft[k-1] - rht[k-1]; } } else{ ans[i] += lft[Q]; ans[i+1] += rht[Q]; } } for(int i = 1; i <= N; i++){ cout << ans[i] << "\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...