Submission #1264083

#TimeUsernameProblemLanguageResultExecution timeMemory
1264083norman165Snowball (JOI21_ho_t2)C++20
33 / 100
2595 ms1092 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define int long long #define yes() cout << "YES\n" #define no() cout << "NO\n" using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; const int inf = 1e18; const int mod = 1e9 + 7; const int maxn = 1e6; const int mod1 = 998244353; const int mod2 = 1e18 + 1; const int mod3 = 1e9 + 9; const int mod4 = 333333333; const int mod5 = 200000; const int mod6 = 10007; const int k = 3000; const int w = 1e5; const ld EPS = 1e-8; int LOG = 30; void solve() { int n, q; cin >> n >> q; vector<int> a(n); for (int& i : a) cin >> i; vector<int> l = a, r = a; vector<int> ans(n); vector<int> prime = a; while (q--) { int w; cin >> w; if (w == 0) continue; if (w < 0) { w = -w; ans[0] += max(0ll, l[0] - prime[0] + w); prime[0] -= w; l[0] = min(l[0], prime[0]); for (int i = 1; i < n; i++) { int x = prime[i] - w; if (l[i] > x) { int l1 = max(r[i - 1], x), r1 = l[i]; ans[i] += max(0ll, r1 - l1); } prime[i] -= w; l[i] = min(l[i], prime[i]); } } else { ans[n - 1] += max(0ll, prime[n - 1] + w - r[n - 1]); prime[n - 1] += w; r[n - 1] = max(r[n - 1], prime[n - 1]); for (int i = n - 2; i >= 0; i--) { int x = prime[i] + w; if (r[i] < x) { int l1 = r[i], r1 = min(l[i + 1], x); ans[i] += max(0ll, r1 - l1); } prime[i] += w; r[i] = max(r[i], prime[i]); } } } for (int& i : ans) cout << i << "\n"; } signed main() { // cout.precision(16); ios::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...