Submission #854149

#TimeUsernameProblemLanguageResultExecution timeMemory
854149BrineTwSnowball (JOI21_ho_t2)C++14
100 / 100
86 ms11388 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> #define debug(x) cerr << #x << ' ' << x << '\n' #define endl '\n' using namespace std; const int M = 1e9 + 7; typedef long long ll; int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int N, Q; cin >> N >> Q; vector<ll> x(N); vector<ll> w(Q); for (auto& n: x) cin >> n; for (auto& n: w) cin >> n; vector<ll> snow(N - 1); for (int i = 1; i < N; i++) { snow[i - 1] = x[i] - x[i - 1]; } vector<ll> left(Q + 1); vector<ll> right(Q + 1); ll cur = 0; for (int i = 1; i <= Q; i++) { cur += w[i - 1]; left[i] = min(left[i - 1], cur); right[i] = max(right[i - 1], cur); } for (int i = 0; i <= Q; i++) { left[i] = abs(left[i]); } vector<ll> ans(N); for (int i = 0; i < N - 1; i++) { ll l = 0, m, r = Q; while (r - l > 1) { m = l + r >> 1; (left[m] + right[m] < snow[i] ? l : r) = m; } ans[i] += right[l]; ans[i + 1] += left[l]; if (w[l] < 0) { ans[i + 1] -= left[l]; ans[i + 1] += min(left[r], snow[i] - right[r]); } else { ans[i] -= right[l]; ans[i] += min(right[r], snow[i] - left[r]); } } ans[0] += left.back(); ans.back() += right.back(); for (auto& n: ans) cout << n << '\n'; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:45:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |             m = l + r >> 1;
      |                 ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...