Submission #1031976

#TimeUsernameProblemLanguageResultExecution timeMemory
1031976mnieplowiczSnowball (JOI21_ho_t2)C++14
0 / 100
1 ms568 KiB
#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; vector<long long> v(n), mini(q, 0), maxi(q, 0), Q(q); for(int i = 0; i < n; i++) cin >> v[i]; long long sum = 0; for(int i = 0; i < q; i++){ cin >> Q[i]; sum += Q[i]; if(i == 0){ mini[i] = min(0ll, sum); maxi[i] = max(0ll, sum); continue; } mini[i] = min(mini[i - 1], sum); maxi[i] = max(maxi[i - 1], sum); } /*for(int i = 0; i <q; i++) cout << mini[i] << " "; cout << '\n'; for(int i = 0; i <q; i++) cout << maxi[i] << " "; cout << '\n';*/ auto bs = [&](int i){ int l = 0, r = q; while(l + 1 < r){ int mid = (l + r) / 2; if(v[i + 1] - v[i] > maxi[mid] - mini[mid]) l = mid; else r = mid; } return l; }; vector<long long> res(n); for(int i = 0; i < n - 1; i++){ int x = bs(i); //cerr << i << ": " << x <<" " << mini[x] << " " << maxi[x]<< '\n'; res[i] += maxi[x]; res[i + 1] -= mini[x]; int dif = 0; if(x != q - 1) dif = v[i + 1] - v[i] - (maxi[x] - mini[x]); if(dif and Q[x + 1] > 0) res[i] += dif; if(dif and Q[x + 1] <= 0) res[i + 1] += dif; //cerr << res[i] << " " << res[i+1] << '\n'; } res[0] -= mini[q - 1]; res[n - 1] += maxi[q - 1]; for(auto a : res) cout << a << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...