Submission #392494

#TimeUsernameProblemLanguageResultExecution timeMemory
392494bayemirovSnowball (JOI21_ho_t2)C++17
100 / 100
2273 ms25020 KiB
#include <bits/stdc++.h> #define ll long long #define all(x) x.begin(), x.end() #define pb push_back #define pii pair<int, int> #define fr first #define sc second using namespace std; const int N = 2e5 + 1; int n, q; ll a[N], d[N], p[N], pref[N], pos2[N], qr[N], pos1[N]; int t[N * 4], shift = 1, lg[2 * N], prmn[N + 500], sufmn[N + 500]; vector<ll> all; int get(ll l, ll r) { if (l == 1) return prmn[r]; else return sufmn[l]; } bool check(int pos, ll m) { int j = -1; ll need = m - a[pos]; need = lower_bound(all(all), need) - all.begin() + 1; j = get(need, N); int k = -1; need = m - a[pos + 1]; need = lower_bound(all(all), need) - all.begin(); k = get(1, need); if (j == 1e9) return false; if (j > k) return false; return true; } bool check2(int pos, ll m) { int j = - 1; ll need = m - a[pos]; need = upper_bound(all(all), need) - all.begin(); j = get(1, need); int k = -1; need = m - a[pos - 1]; need = upper_bound(all(all), need) - all.begin() + 1; k = get(need, N); if (j == 1e9) return false; if (j > k) return false; return true; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for (int i = 0; i < 4 * N; i++) t[i] = 1e9; for (int i = 1; i <= n; i++) cin >> a[i]; ll x = *min_element(a + 1, a + 1 + n); ll mn2 = 1e18; for (int i = 1; i <= q; i++) cin >> d[i]; for (int i = 1; i <= q; i++) p[i] = p[i - 1] + d[i], all.pb(p[i]); for (int i = 1; i <= q; i++) mn2 = min(mn2, x + p[i]); for (int i = 1; i <= n; i++) a[i] += abs(mn2) + 1; sort(all(all)); all.resize(unique(all(all)) - all.begin()); for (int i = 1; i <= q; i++) pref[i] = lower_bound(all(all), p[i]) - all.begin() + 1; for (int i = 1; i <= q; i++) t[pref[i]] = min(t[pref[i]], i); fill(prmn, prmn + N + 500, 1e9); fill(sufmn, sufmn + N + 500, 1e9); for (int i = 1; i <= N; i++) { prmn[i] = min(prmn[i - 1], t[i]); } for (int i = N; i >= 1; i--) { sufmn[i] = min(sufmn[i + 1], t[i]); } for (int i = 1; i < n; i++) { ll l = a[i] + 1; ll r = a[i + 1]; ll ans = -1; while (l <= r) { ll m = (l + r) / 2; if (check(i, m)) l = m + 1, ans = m; else r = m - 1; } pos1[i] = ans; } for (int i = 2; i <= n; i++) { ll l = a[i - 1]; ll r = a[i] - 1; ll ans = -1; while (l <= r) { ll m = (l + r) / 2; if (check2(i, m)) r = m - 1, ans = m; else l = m + 1; } pos2[i] = ans; } for (int i = 1; i < n; i++) if (pos1[i] != -1) qr[i] += pos1[i] - a[i]; for (int i = 2; i <= n; i++) if (pos2[i] != -1) qr[i] += a[i] - pos2[i]; qr[1] += abs(min(0ll, *min_element(p + 1, p + 1 + q))); qr[n] += max(0ll, *max_element(p + 1, p + 1 + q)); for (int i = 1; i <= n; i++) cout << qr[i] << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...